글 읽기 - 반례를 모르겠습니다.

devbelly 3년 전 1

게시판 반례는 모두 통과하였습니다

https://acm.timus.ru/problem.a...

위 두 링크는 조금 다르지만 비슷한 문제인데, 여기도 넣어보니 다 맞았습니다.

혹시 제 코드에 반례가 무엇인지 알려주시면 정말 감사하겠습니다.

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

#define int long long

struct edge {
    int u, v, w;
};

typedef pair<int, int> pii;

const int MAXE = 2e5;
const int MAXV = 5e4;

int V, E, cnt, len;

edge edges[MAXE];
bool used[MAXE];
int par[MAXV];
int top[MAXV], pa[MAXV], sz[MAXV], idx[MAXV];

vector<vector<int>> adj;
vector<pii> tree;
int dfs(int here) {
    sz[here] = 1;
    for (auto& there : adj[here]) {
        if (pa[here] ^ there) {
            pa[there] = here;
            sz[here] += dfs(there);
            int& h = adj[here][0];

            if (h == pa[here] || sz[h] < sz[there])
                swap(h, there);
        }
    }
    return sz[here];
}

void hld(int here) {
    idx[here] = cnt++;
    for (auto there : adj[here]) {
        if (there ^ pa[here]) {
            top[there] = there == adj[here][0] ? top[here] : there;
            hld(there);
        }
    }
}

void init() {
    //사용한 간선을 세그먼트 트리에 추가
    rep(i, E) {
        if (used[i]) {
            auto& [u, v, w] = edges[i];

            if (pa[u] == v)
                swap(u, v);

            tree[len + idx[v]].first = w;
            tree[len + idx[v]].second = -1;
        }
    }
    //first : 경로상 가장 큰 간선 찾기 위함
    //second : 경로상 두번째로 큰 간선을 찾기 위함
    for (int i = len - 1; i > 0; --i) {
        vector<int> vt;
        auto [a, b] = tree[i << 1];
        auto [c, d] = tree[i << 1 | 1];
        vt.emplace_back(a);
        vt.emplace_back(b);
        vt.emplace_back(c);
        vt.emplace_back(d);

        sort(vt.rbegin(), vt.rend());
        tree[i].first = vt[0];
        auto iter = upper_bound(vt.begin(), vt.end(), vt[0], greater<int>());
        if (iter == vt.end()) {

            continue;
        }
        tree[i].second = *upper_bound(vt.begin(), vt.end(), vt[0], greater<int>());
        /*cout << "넣을떄 이거 넣는다" <<' '<<i<< ' ' << tree[i].first << ' ' << tree[i].second << '\n';*/
    }
}

int find(int x) {
    return (par[x] < 0) ? x : (par[x] = find(par[x]));
}

pii query1(int l, int r) {
    l += len;
    r += len;

    vector<int> ret;
    ret.emplace_back(-1);
    for (; l <= r; l >>= 1, r >>= 1) {
        if (l & 1) {
            ret.emplace_back(tree[l].first);
            ret.emplace_back(tree[l++].second);
        }
        if (!(r & 1)) {
            ret.emplace_back(tree[r].first);
            ret.emplace_back(tree[r--].second);
        }
    }
    sort(ret.rbegin(), ret.rend());
    if (ret[0] == -1) {
        return { -1, -1 };
    }
    return { ret[0], *upper_bound(ret.begin(), ret.end(), ret[0], greater<int>()) };
}

pii solve(int u, int v) {
    vector<int> ret;
    ret.emplace_back(-1);

    while (top[u] ^ top[v]) {
        if (sz[top[u]] < sz[top[v]])
            swap(u, v);
        pii res = query1(idx[top[v]], idx[v]);
        ret.emplace_back(res.first);
        ret.emplace_back(res.second);
        v = pa[top[v]];
    }
    if (idx[u] > idx[v])
        swap(u, v); //u가 더 높음
    pii res = query1(idx[u] + 1, idx[v]);
    ret.emplace_back(res.first);
    ret.emplace_back(res.second);
    sort(ret.rbegin(), ret.rend());
    if (ret[0] == -1) {

        return { -1, -1 };
    }
    return { ret[0], *upper_bound(ret.begin(), ret.end(), ret[0], greater<int>()) };
}

signed main() {

    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> V >> E;
    len = pow(2, ceil(log2(V)));
    tree.resize(len << 1, { -1, -1 });
    adj.resize(V);
    rep(i, E) {
        auto& [u, v, w] = edges[i];
        cin >> u >> v >> w;
        --u, --v;
    }

    memset(par, -1, sizeof(par));
    sort(edges, edges + E, [&](auto& a, auto& b) { return a.w < b.w; });

    int ans = 0;

    rep(i, E) {
        auto [u, v, w] = edges[i];
        int a = find(u);
        int b = find(v);

        if (a ^ b) {
            used[i] = true;

            adj[u].emplace_back(v);
            adj[v].emplace_back(u);

            par[a] = b;
            ans += w;
        }
    }

    dfs(0);
    hld(0);
    init();

    int ret = LLONG_MAX;

    rep(i, E) {
        if (!used[i]) {
            auto [u, v, w] = edges[i];

            auto [fir, sec] = solve(u, v);

            if (fir != -1 && fir != w) {

                ret = min(ret, ans - fir + w);
            }
            else if (sec != w && sec != -1) {

                ret = min(ret, ans - sec + w);
            }
        }
    }
    cout << ((ret == LLONG_MAX) ? -1 : ret);
    return 0;
}

3587jjh 3년 전 1

반례입니다.

3 2
1 2 1
1 2 6

devbelly 3년 전 0

아니 형님 너무 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 모르겠습니다.

devbelly 3년 전 1

3587jjh 3년 전 1

devbelly 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말