oj.uz

Submission #999494

# Submission time Handle Problem Language Result Execution time Memory
999494 2024-06-15T15:43:17 Z bachhoangxuan Parachute rings (IOI12_rings) C++17
0 / 100
 189 ms 82100 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;

int N,deg[maxn];
struct dsu{
    bool check=true;
    int cnt,par[maxn],sz[maxn],dd[maxn];
    dsu(){};
    void init(){
        cnt=N;check=true;
        for(int i=0;i<N;i++) par[i]=i,sz[i]=1;
    }
    int findpar(int u){
        if(u!=par[u]) return par[u]=findpar(par[u]);
        return u;
    }
    void unions(int u,int v){
        dd[u]++,dd[v]++;
        if(dd[u]>=3 || dd[v]>=3) check=false,cnt=0;
        u=findpar(u);v=findpar(v);
        if(u==v){
            if(!check) cnt=0;
            else cnt=sz[u];
            check=false;
            return;
        }
        if(sz[u]<sz[v]) swap(u,v);
        sz[u]+=sz[v];par[v]=u;
    }
};
int mx=0;
vector<pair<int,int>> e;
vector<int> V;
dsu D[5],S;

void Init(int N_) {
  N = N_;
  S.init();
}

void Link(int A, int B) {
    deg[A]++;deg[B]++;
    mx=max({mx,deg[A],deg[B]});
    e.push_back({A,B});
    S.unions(A,B);
    if(mx==3){
        if(V.empty()){
            int x=A;
            if(deg[x]!=3) x=B;
            for(auto [u,v]:e) if(u==x || v==x) V.push_back(u^v^x);
            V.push_back(x);
            for(int i=0;i<4;i++){
                D[i].init();
                for(auto [u,v]:e) if(u!=V[i] && v!=V[i]) D[i].unions(u,v);
            }
        }
        else{
            for(int i=0;i<4;i++){
                if(A==V[i] || B==V[i]) continue;
                D[i].unions(A,B);
            }
        }
    }
}

int CountCritical() {
    if(mx<=2) return S.cnt;
    else if(mx>3) return 0;
    int total=0;
    for(int i=0;i<4;i++){
        total+=D[i].check;
        //if(D[i].check) cout << '*' << V[i] << '\n';
    }
    return total;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Incorrect 4 ms 33372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 34220 KB Output is correct
2 Incorrect 189 ms 82100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Incorrect 4 ms 33372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Incorrect 4 ms 33372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Incorrect 4 ms 33372 KB Output isn't correct
3 Halted 0 ms 0 KB -