oj.uz

Submission #476053

# Submission time Handle Problem Language Result Execution time Memory
476053 2021-09-24T16:46:12 Z blue Pipes (CEOI15_pipes) C++17
20 / 100
 629 ms 4684 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(subtree[u] < subtree[v]) swap(u, v);
        parent[v] = u;
        subtree[u] += subtree[v];
    }
};

const int maxN = 100'00;
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] = 1; //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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1612 KB Output is correct
2 Incorrect 1 ms 1612 KB Wrong number of edges

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1740 KB Output is correct
2 Incorrect 7 ms 1740 KB Wrong number of edges

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 1784 KB Output is correct
2 Correct 254 ms 1740 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 2056 KB Output is correct
2 Correct 629 ms 2016 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 3532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 4172 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 4400 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 4664 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 4684 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 4628 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -