oj.uz

답안 #476051

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
476051 2021-09-24T16:45:28 Z blue Pipes (CEOI15_pipes) C++17
0 / 100
 4488 ms 28632 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'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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 13600 KB Output is correct
2 Incorrect 11 ms 13540 KB Wrong number of edges

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 13812 KB Output is correct
2 Incorrect 15 ms 13712 KB Wrong number of edges

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 292 ms 13772 KB Output is correct
2 Runtime error 302 ms 19016 KB Memory limit exceeded

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 513 ms 13900 KB Output is correct
2 Runtime error 581 ms 25380 KB Memory limit exceeded

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 940 ms 14564 KB Output is correct
2 Runtime error 753 ms 28632 KB Memory limit exceeded

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1255 ms 16384 KB Output is correct
2 Runtime error 1281 ms 17384 KB Memory limit exceeded

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2096 ms 16804 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3234 ms 17540 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3898 ms 17536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4488 ms 17340 KB Memory limit exceeded
2 Halted 0 ms 0 KB -