Submission #476051

#	Time	Username	Problem	Language	Result	Execution time	Memory
476051		blue	Pipes (CEOI15_pipes)	C++17	0 / 100	4488 ms	28632 KiB

pipes

#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'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] = 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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10