oj.uz

Submission #1035599

# Submission time Handle Problem Language Result Execution time Memory
1035599 2024-07-26T12:21:46 Z Warinchai Parachute rings (IOI12_rings) C++14
37 / 100
 1764 ms 247524 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){
    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(tvis[A])dfs(A,from[A]);
    if(tvis[B])dfs(B,from[B]);
    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 {
                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 51 ms 117840 KB Output is correct
2 Correct 49 ms 118312 KB Output is correct
3 Correct 49 ms 118352 KB Output is correct
4 Correct 48 ms 117844 KB Output is correct
5 Correct 52 ms 118108 KB Output is correct
6 Correct 51 ms 118516 KB Output is correct
7 Correct 49 ms 118096 KB Output is correct
8 Correct 50 ms 118100 KB Output is correct
9 Correct 54 ms 118352 KB Output is correct
10 Correct 57 ms 118360 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 168120 KB Output is correct
2 Correct 690 ms 195360 KB Output is correct
3 Correct 368 ms 183648 KB Output is correct
4 Correct 859 ms 217680 KB Output is correct
5 Correct 999 ms 223516 KB Output is correct
6 Correct 1764 ms 247524 KB Output is correct
7 Correct 367 ms 183448 KB Output is correct
8 Correct 992 ms 208724 KB Output is correct
9 Correct 901 ms 214864 KB Output is correct
10 Correct 691 ms 215996 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 117840 KB Output is correct
2 Correct 49 ms 118312 KB Output is correct
3 Correct 49 ms 118352 KB Output is correct
4 Correct 48 ms 117844 KB Output is correct
5 Correct 52 ms 118108 KB Output is correct
6 Correct 51 ms 118516 KB Output is correct
7 Correct 49 ms 118096 KB Output is correct
8 Correct 50 ms 118100 KB Output is correct
9 Correct 54 ms 118352 KB Output is correct
10 Correct 57 ms 118360 KB Output is correct
11 Correct 58 ms 118356 KB Output is correct
12 Correct 57 ms 118868 KB Output is correct
13 Correct 81 ms 118864 KB Output is correct
14 Incorrect 69 ms 118608 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 117840 KB Output is correct
2 Correct 49 ms 118312 KB Output is correct
3 Correct 49 ms 118352 KB Output is correct
4 Correct 48 ms 117844 KB Output is correct
5 Correct 52 ms 118108 KB Output is correct
6 Correct 51 ms 118516 KB Output is correct
7 Correct 49 ms 118096 KB Output is correct
8 Correct 50 ms 118100 KB Output is correct
9 Correct 54 ms 118352 KB Output is correct
10 Correct 57 ms 118360 KB Output is correct
11 Correct 58 ms 118356 KB Output is correct
12 Correct 57 ms 118868 KB Output is correct
13 Correct 81 ms 118864 KB Output is correct
14 Incorrect 69 ms 118608 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 117840 KB Output is correct
2 Correct 49 ms 118312 KB Output is correct
3 Correct 49 ms 118352 KB Output is correct
4 Correct 48 ms 117844 KB Output is correct
5 Correct 52 ms 118108 KB Output is correct
6 Correct 51 ms 118516 KB Output is correct
7 Correct 49 ms 118096 KB Output is correct
8 Correct 50 ms 118100 KB Output is correct
9 Correct 54 ms 118352 KB Output is correct
10 Correct 57 ms 118360 KB Output is correct
11 Correct 323 ms 168120 KB Output is correct
12 Correct 690 ms 195360 KB Output is correct
13 Correct 368 ms 183648 KB Output is correct
14 Correct 859 ms 217680 KB Output is correct
15 Correct 999 ms 223516 KB Output is correct
16 Correct 1764 ms 247524 KB Output is correct
17 Correct 367 ms 183448 KB Output is correct
18 Correct 992 ms 208724 KB Output is correct
19 Correct 901 ms 214864 KB Output is correct
20 Correct 691 ms 215996 KB Output is correct
21 Correct 58 ms 118356 KB Output is correct
22 Correct 57 ms 118868 KB Output is correct
23 Correct 81 ms 118864 KB Output is correct
24 Incorrect 69 ms 118608 KB Output isn't correct
25 Halted 0 ms 0 KB -