oj.uz

Submission #1035651

# Submission time Handle Problem Language Result Execution time Memory
1035651 2024-07-26T12:57:02 Z Warinchai Parachute rings (IOI12_rings) C++14
37 / 100
 1389 ms 253888 KB 
#include<bits/stdc++.h>
using namespace std;
int N;
set<int>s[2000005];
int cur=0;
int p[1000005];
int in[1000005];
int vis[1000005];
int tvis[1000005];
int cycle=0;
int from[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++)from[i]=-1,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);
}
void dfs(int u,int p=-1){
    //cerr<<"dfs:"<<u<<" "<<p<<"\n";
    from[u]=p;
    tvis[u]=1;
    for(auto x:adj[u])if(x!=p&&tvis[x]==0)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(tvis[A])dfs(A,from[A]);
    if(tvis[B])dfs(B,from[B]);
    //cerr<<"FROMS:\n";
    //for(int i=0;i<N;i++)cerr<<from[i]<<" ";
    //cerr<<"\n\n";
    if(fp(A)==fp(B)){
        if(cycle){
            if(vis[A]&&vis[B])add({A,B});
            else if(!vis[A]&&!vis[B])return void(cur++);
            else {
                //cerr<<"work\n";
                if(vis[A])swap(A,B);
                int temp=A;
                //cerr<<"going back:\n";
                while(!vis[temp]){
                    //cerr<<temp<<"\n";
                    vis[temp]=1;
                    temp=from[temp];
                }
                //cerr<<"conncection:"<<B<<" "<<temp<<"\n";
                add({B,temp});
            }
        }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() {
    //cerr<<s[cur].size()<<"info:\n";
    //for(auto x:s[cur])cerr<<x<<" ";
    //cerr<<"\n";
    return s[cur].size();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 117796 KB Output is correct
2 Correct 50 ms 118152 KB Output is correct
3 Correct 49 ms 118096 KB Output is correct
4 Correct 48 ms 117844 KB Output is correct
5 Correct 49 ms 118096 KB Output is correct
6 Correct 50 ms 118616 KB Output is correct
7 Correct 47 ms 118036 KB Output is correct
8 Correct 49 ms 118100 KB Output is correct
9 Correct 49 ms 118616 KB Output is correct
10 Correct 49 ms 118356 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 164912 KB Output is correct
2 Correct 661 ms 189776 KB Output is correct
3 Correct 366 ms 176980 KB Output is correct
4 Correct 749 ms 210724 KB Output is correct
5 Correct 817 ms 230408 KB Output is correct
6 Correct 1389 ms 253888 KB Output is correct
7 Correct 347 ms 189268 KB Output is correct
8 Correct 709 ms 214352 KB Output is correct
9 Correct 788 ms 221012 KB Output is correct
10 Correct 581 ms 222124 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 117796 KB Output is correct
2 Correct 50 ms 118152 KB Output is correct
3 Correct 49 ms 118096 KB Output is correct
4 Correct 48 ms 117844 KB Output is correct
5 Correct 49 ms 118096 KB Output is correct
6 Correct 50 ms 118616 KB Output is correct
7 Correct 47 ms 118036 KB Output is correct
8 Correct 49 ms 118100 KB Output is correct
9 Correct 49 ms 118616 KB Output is correct
10 Correct 49 ms 118356 KB Output is correct
11 Correct 49 ms 118268 KB Output is correct
12 Correct 52 ms 118924 KB Output is correct
13 Correct 51 ms 118748 KB Output is correct
14 Incorrect 49 ms 118688 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 117796 KB Output is correct
2 Correct 50 ms 118152 KB Output is correct
3 Correct 49 ms 118096 KB Output is correct
4 Correct 48 ms 117844 KB Output is correct
5 Correct 49 ms 118096 KB Output is correct
6 Correct 50 ms 118616 KB Output is correct
7 Correct 47 ms 118036 KB Output is correct
8 Correct 49 ms 118100 KB Output is correct
9 Correct 49 ms 118616 KB Output is correct
10 Correct 49 ms 118356 KB Output is correct
11 Correct 49 ms 118268 KB Output is correct
12 Correct 52 ms 118924 KB Output is correct
13 Correct 51 ms 118748 KB Output is correct
14 Incorrect 49 ms 118688 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 117796 KB Output is correct
2 Correct 50 ms 118152 KB Output is correct
3 Correct 49 ms 118096 KB Output is correct
4 Correct 48 ms 117844 KB Output is correct
5 Correct 49 ms 118096 KB Output is correct
6 Correct 50 ms 118616 KB Output is correct
7 Correct 47 ms 118036 KB Output is correct
8 Correct 49 ms 118100 KB Output is correct
9 Correct 49 ms 118616 KB Output is correct
10 Correct 49 ms 118356 KB Output is correct
11 Correct 340 ms 164912 KB Output is correct
12 Correct 661 ms 189776 KB Output is correct
13 Correct 366 ms 176980 KB Output is correct
14 Correct 749 ms 210724 KB Output is correct
15 Correct 817 ms 230408 KB Output is correct
16 Correct 1389 ms 253888 KB Output is correct
17 Correct 347 ms 189268 KB Output is correct
18 Correct 709 ms 214352 KB Output is correct
19 Correct 788 ms 221012 KB Output is correct
20 Correct 581 ms 222124 KB Output is correct
21 Correct 49 ms 118268 KB Output is correct
22 Correct 52 ms 118924 KB Output is correct
23 Correct 51 ms 118748 KB Output is correct
24 Incorrect 49 ms 118688 KB Output isn't correct
25 Halted 0 ms 0 KB -