oj.uz

Submission #54813

# Submission time Handle Problem Language Result Execution time Memory
54813 2018-07-05T07:10:53 Z 노영훈(#1508) Pipes (CEOI15_pipes) C++11
0 / 100
 612 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;

int n, m;

int par[MX], dep[MX];
pii pe[MX];
set<int> G[MX];
int tree[MX], sz[MX];
int U[MX];
set<pii> ans;

int find(int x){
    return x==U[x] ? x : U[x]=find(U[x]);
}
void unite(int x, int y){
    if(find(x)==find(y)) return;
    U[U[x]]=U[y];
}

void dfs(int v, int p, int d){
    dep[v]=d; par[v]=p; tree[v]=tree[p];
    for(int x:G[v]){
        if(x==p) continue;
        dfs(x,v,d+1);
    }
}
// initialzing for merge (dep, par)
void merge(int x, int y, pii e){
    if(sz[tree[x]]<sz[tree[y]]) swap(x,y);
    sz[tree[x]]+=sz[tree[y]];
    G[x].insert(y);
    G[y].insert(x);
    dfs(y, x, dep[x]+1);
    pe[y]=e;
}
// place y below x

void erase(pii e){
    ans.erase(e);
    swap(e.first, e.second);
    ans.erase(e);
}

void lca(int u, int v){
    if(dep[u]<dep[v]) swap(u,v);
    vector<int> X;
    while(dep[u]>dep[v]){
        X.push_back(u);
        u=par[u];
    }
    while(u!=v){
        X.push_back(u); X.push_back(v);
        u=par[u]; v=par[v];
    }
    X.push_back(u);

    int p=find(u);
    int pp=par[u]; pii ppe=pe[u];
    set<int> adj;

    for(int x:X){
        unite(x,p);
        if(x!=u) erase(pe[x]);
        par[x]=0, pe[x]={0,0};
    }

    for(int v:X){
        for(int x:G[v]){
            if(find(x)!=find(v)){
                adj.insert(x);
                G[x].erase(v);
                G[x].insert(p);
                if(par[x]==v) par[x]=p;
            }
        }
    }
    G[p]=adj;
    par[p]=pp; pe[p]=ppe;
}

void ddfs(int v, int p){
    cout<<v<<' ';
    for(int x:G[v]){
        if(x==p) continue;
        ddfs(x,v);
    }
    cout<<"out\n";
}

void debug(){
    for(int i=1; i<=n; i++){
        if(find(i)!=i) continue;
        cout<<i<<": ";
        for(int x:G[i]) cout<<x<<' ';
        cout<<'\n';
    }
    cout<<'\n';
}

void init(){
    for(int i=1; i<=n; i++)
        U[i]=i, sz[i]=1, par[i]=0, tree[i]=i, dep[i]=0;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    init();
    for(int i=1; i<=m; i++){
        int u, v; cin>>u>>v;
        int x=find(u), y=find(v);
        if(tree[x]==tree[y]){
            lca(x, y);
        }
        else{
            merge(x, y, {u,v});
        }
        // debug();
        // if same tree
        //   delete all edges in its way and current edge
        //   also unite all vertices
        // if not
        //   merge two trees. put smaller one to bigger one

    }
    for(int i=1; i<=n; i++){
        if(find(i)!=i) continue;
        if(pe[i]==pii(0,0)) continue;
        cout<<pe[i].first<<' '<<pe[i].second<<'\n';
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 268 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 612 ms 5680 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 121 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 335 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 103 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 163 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 166 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 181 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 186 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 150 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -