oj.uz

Submission #1035493

# Submission time Handle Problem Language Result Execution time Memory
1035493 2024-07-26T11:34:26 Z Warinchai Parachute rings (IOI12_rings) C++14
20 / 100
 837 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
int N;
set<int>s[3000005];
int cur=0;
int p[1000005];
int in[1000005];
int fp(int a){return p[a]==a?a:p[a]=fp(p[a]);}
void un(int a,int b){p[fp(b)]=fp(a);}
vector<int>adj[1000005];
void Init(int N_) {
    N = N_;
    for(int i=0;i<N;i++)s[0].insert(i),p[i]=i;
}
void add(vector<int>v){
    cur++;
    for(auto x:v){
        if(s[cur-1].count(x))s[cur-1].erase(x),s[cur].insert(x);
    }
    //cerr<<s[cur].size()<<":\n";
    //for(auto x:s[cur])cerr<<x<<" ";
    //cerr<<"\n";
}
void add_3(int u){
    vector<int>temp;
    temp.push_back(u);
    for(auto x:adj[u]){
        temp.push_back(x);
    }
    add(temp);
}
int vis[1000005];
int tvis[1000005];
int cycle=0;
int from[1000005];
void dfs(int u,int p=-1){
    if(tvis[u])return;
    //cerr<<"dfs:"<<u<<" "<<p<<"\n";
    from[u]=p;
    tvis[u]=1;
    for(auto x:adj[u])if(x!=p)dfs(x,u);
}
void Link(int A, int B) {
    if(s[cur].size()==0)return;
    in[A]++;
    in[B]++;
    adj[A].push_back(B);
    adj[B].push_back(A);
    if(vis[A])from[B]=A;
    if(vis[B])from[A]=B;
    if(fp(A)==fp(B)){
        if(cycle){
            if(vis[A]&&vis[B])return add({A,B});
            if(!vis[A]&&!vis[B])return void(cur++);
            if(vis[A])swap(A,B);
            int temp=A;
            while(!vis[temp]){
                vis[temp]=1;
                temp=from[temp];
            }
            add({A,B});
        }else{
            cycle=1;
            dfs(A,B);
            int temp=B;
            vector<int>loop;
            while(temp!=A)/*cerr<<"re loop:"<<temp<<"\n",*/loop.push_back(temp),vis[temp]++,temp=from[temp];
            loop.push_back(A);
            vis[A]++;
            //cerr<<"in loop:\n";
            //for(auto x:loop)cerr<<x<<" ";
            //cerr<<"\n";
            add(loop);
        }
    }
    un(A,B);
    if(in[A]==3)add_3(A);
    if(in[B]==3)add_3(B);
    if(in[A]>3)add({A});
    if(in[B]>3)add({B});
}

int CountCritical() {
    return s[cur].size();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 164692 KB Output is correct
2 Correct 98 ms 165200 KB Output is correct
3 Correct 101 ms 165228 KB Output is correct
4 Correct 64 ms 164944 KB Output is correct
5 Correct 86 ms 165156 KB Output is correct
6 Correct 76 ms 165460 KB Output is correct
7 Correct 76 ms 164944 KB Output is correct
8 Correct 73 ms 166948 KB Output is correct
9 Correct 75 ms 166932 KB Output is correct
10 Correct 74 ms 167024 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 214352 KB Output is correct
2 Correct 643 ms 244960 KB Output is correct
3 Correct 416 ms 232532 KB Output is correct
4 Correct 837 ms 262144 KB Output is correct
5 Runtime error 751 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 164692 KB Output is correct
2 Correct 98 ms 165200 KB Output is correct
3 Correct 101 ms 165228 KB Output is correct
4 Correct 64 ms 164944 KB Output is correct
5 Correct 86 ms 165156 KB Output is correct
6 Correct 76 ms 165460 KB Output is correct
7 Correct 76 ms 164944 KB Output is correct
8 Correct 73 ms 166948 KB Output is correct
9 Correct 75 ms 166932 KB Output is correct
10 Correct 74 ms 167024 KB Output is correct
11 Correct 83 ms 166992 KB Output is correct
12 Correct 77 ms 167508 KB Output is correct
13 Correct 76 ms 167632 KB Output is correct
14 Incorrect 74 ms 167252 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 164692 KB Output is correct
2 Correct 98 ms 165200 KB Output is correct
3 Correct 101 ms 165228 KB Output is correct
4 Correct 64 ms 164944 KB Output is correct
5 Correct 86 ms 165156 KB Output is correct
6 Correct 76 ms 165460 KB Output is correct
7 Correct 76 ms 164944 KB Output is correct
8 Correct 73 ms 166948 KB Output is correct
9 Correct 75 ms 166932 KB Output is correct
10 Correct 74 ms 167024 KB Output is correct
11 Correct 83 ms 166992 KB Output is correct
12 Correct 77 ms 167508 KB Output is correct
13 Correct 76 ms 167632 KB Output is correct
14 Incorrect 74 ms 167252 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 164692 KB Output is correct
2 Correct 98 ms 165200 KB Output is correct
3 Correct 101 ms 165228 KB Output is correct
4 Correct 64 ms 164944 KB Output is correct
5 Correct 86 ms 165156 KB Output is correct
6 Correct 76 ms 165460 KB Output is correct
7 Correct 76 ms 164944 KB Output is correct
8 Correct 73 ms 166948 KB Output is correct
9 Correct 75 ms 166932 KB Output is correct
10 Correct 74 ms 167024 KB Output is correct
11 Correct 389 ms 214352 KB Output is correct
12 Correct 643 ms 244960 KB Output is correct
13 Correct 416 ms 232532 KB Output is correct
14 Correct 837 ms 262144 KB Output is correct
15 Runtime error 751 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -