oj.uz

답안 #476060

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
476060 2021-09-24T17:04:49 Z blue Pipes (CEOI15_pipes) C++17
40 / 100
 1347 ms 20940 KB 
#include <iostream>
#include <vector>
#include <set>
using namespace std;

struct disjoint_set
{
    int N;
    vector<int> parent;
    vector<int> subtree;

    disjoint_set()
    {
        ;
    }

    disjoint_set(int N_)
    {
        N = N_;
        parent = vector<int>(1+N);
        subtree = vector<int>(1+N, 1);
        for(int i = 1; i <= N; i++) parent[i] = i;
    }

    int root(int u)
    {
        int v = u;
        while(parent[v] != v) v = parent[v];
        parent[u] = v;
        return parent[u];
    }

    bool connected(int u, int v)
    {
        return root(u) == root(v);
    }

    void join(int u, int v)
    {
        u = root(u);
        v = root(v);
        if(u == v) return;
        if(subtree[u] < subtree[v]) swap(u, v);
        parent[v] = u;
        subtree[u] += subtree[v];
    }
};

const int maxN = 70'000;
const int logN = 16;

vector<int> edge[1+maxN];
vector<int> depth(1+maxN);
vector< vector<int> > anc(1+maxN, vector<int>(1+logN, -1));

void dfs(int u)
{
    for(int v: edge[u])
    {
        if(anc[u][0] == v) continue;
        anc[v][0] = u;
        depth[v] = 1+depth[u];

        dfs(v);
    }
}

int lca(int u, int v)
{
    if(depth[u] > depth[v]) swap(u, v);
    for(int e = logN; e >= 0; e--)
        if((1 << e) & (depth[v] - depth[u]))
            v = anc[v][e];

    if(u == v) return u;

    for(int e = logN; e >= 0; e--)
    {
        if(anc[u][e] != anc[v][e])
        {
            u = anc[u][e];
            v = anc[v][e];
        }
    }
    return anc[u][0];
}



vector<int> token(1+maxN, 0);

int dfs2(int u)
{
    int T = token[u];
    for(int v: edge[u])
    {
        if(anc[u][0] == v) continue;

        int D = dfs2(v);
        if(!D) cout << u << ' ' << v << '\n';
        T += D;
    }
    return T;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    disjoint_set DSU(N);

    for(int j = 1; j <= M; j++)
    {
        int u, v;
        cin >> u >> v;
        if(!DSU.connected(u, v))
        {
            edge[u].push_back(v);
            edge[v].push_back(u);
            DSU.join(u, v);
        }
    }

    for(int i = 1; i <= N; i++)
    {
        if(DSU.root(i) == i)
        {
            anc[i][0] = i; //Be careful with this!!!
            depth[i] = 0;
            dfs(i);
        }
    }
    // cerr << "check\n";
    //
    // cerr << "parent: ";
    // for(int i = 1; i <= N; i++) cerr << anc[i][0] << ' ';
    // cerr << '\n';

    for(int e = 1; e <= logN; e++)
    {
        for(int u = 1; u <= N; u++)
        {
            // cerr << e << ' ' << u << '\n';
            anc[u][e] = anc[ anc[u][e-1] ][e-1];
        }
    }

    rewind(stdin);

    cin >> N >> M;

    for(int j = 1; j <= M; j++)
    {
        int u, v;
        cin >> u >> v;

        if(anc[u][0] == v || anc[v][0] == u) continue;

        token[u]++;
        token[v]++;
        token[lca(u,v)] -= 2;
    }

    for(int i = 1; i <= N; i++)
        if(DSU.root(i) == i)
            dfs2(i);
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9548 KB Output is correct
2 Incorrect 8 ms 9548 KB Wrong number of edges

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 9816 KB Output is correct
2 Incorrect 14 ms 9700 KB Wrong number of edges

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 9764 KB Output is correct
2 Correct 264 ms 9768 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 478 ms 10000 KB Output is correct
2 Correct 646 ms 10004 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 813 ms 10572 KB Output is correct
2 Correct 712 ms 10796 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1347 ms 12532 KB Output is correct
2 Correct 1224 ms 12508 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 20620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 20940 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 20872 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 20788 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -