oj.uz

Submission #1035602

# Submission time Handle Problem Language Result Execution time Memory
1035602 2024-07-26T12:23:49 Z Warinchai Parachute rings (IOI12_rings) C++14
37 / 100
 1650 ms 240832 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]&&!tvis[B])dfs(A,from[A]);
    if(tvis[B]&&!tvis[A])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 59 ms 117744 KB Output is correct
2 Correct 53 ms 118096 KB Output is correct
3 Correct 54 ms 118100 KB Output is correct
4 Correct 70 ms 117840 KB Output is correct
5 Correct 49 ms 118080 KB Output is correct
6 Correct 72 ms 118352 KB Output is correct
7 Correct 77 ms 118100 KB Output is correct
8 Correct 52 ms 118100 KB Output is correct
9 Correct 69 ms 118104 KB Output is correct
10 Correct 73 ms 118096 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 164480 KB Output is correct
2 Correct 705 ms 189688 KB Output is correct
3 Correct 404 ms 176980 KB Output is correct
4 Correct 878 ms 210928 KB Output is correct
5 Correct 882 ms 216660 KB Output is correct
6 Correct 1650 ms 240832 KB Output is correct
7 Correct 419 ms 177068 KB Output is correct
8 Correct 827 ms 201824 KB Output is correct
9 Correct 919 ms 207696 KB Output is correct
10 Correct 722 ms 209352 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 117744 KB Output is correct
2 Correct 53 ms 118096 KB Output is correct
3 Correct 54 ms 118100 KB Output is correct
4 Correct 70 ms 117840 KB Output is correct
5 Correct 49 ms 118080 KB Output is correct
6 Correct 72 ms 118352 KB Output is correct
7 Correct 77 ms 118100 KB Output is correct
8 Correct 52 ms 118100 KB Output is correct
9 Correct 69 ms 118104 KB Output is correct
10 Correct 73 ms 118096 KB Output is correct
11 Correct 61 ms 118248 KB Output is correct
12 Correct 57 ms 118712 KB Output is correct
13 Correct 57 ms 118860 KB Output is correct
14 Incorrect 74 ms 118512 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 117744 KB Output is correct
2 Correct 53 ms 118096 KB Output is correct
3 Correct 54 ms 118100 KB Output is correct
4 Correct 70 ms 117840 KB Output is correct
5 Correct 49 ms 118080 KB Output is correct
6 Correct 72 ms 118352 KB Output is correct
7 Correct 77 ms 118100 KB Output is correct
8 Correct 52 ms 118100 KB Output is correct
9 Correct 69 ms 118104 KB Output is correct
10 Correct 73 ms 118096 KB Output is correct
11 Correct 61 ms 118248 KB Output is correct
12 Correct 57 ms 118712 KB Output is correct
13 Correct 57 ms 118860 KB Output is correct
14 Incorrect 74 ms 118512 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 117744 KB Output is correct
2 Correct 53 ms 118096 KB Output is correct
3 Correct 54 ms 118100 KB Output is correct
4 Correct 70 ms 117840 KB Output is correct
5 Correct 49 ms 118080 KB Output is correct
6 Correct 72 ms 118352 KB Output is correct
7 Correct 77 ms 118100 KB Output is correct
8 Correct 52 ms 118100 KB Output is correct
9 Correct 69 ms 118104 KB Output is correct
10 Correct 73 ms 118096 KB Output is correct
11 Correct 361 ms 164480 KB Output is correct
12 Correct 705 ms 189688 KB Output is correct
13 Correct 404 ms 176980 KB Output is correct
14 Correct 878 ms 210928 KB Output is correct
15 Correct 882 ms 216660 KB Output is correct
16 Correct 1650 ms 240832 KB Output is correct
17 Correct 419 ms 177068 KB Output is correct
18 Correct 827 ms 201824 KB Output is correct
19 Correct 919 ms 207696 KB Output is correct
20 Correct 722 ms 209352 KB Output is correct
21 Correct 61 ms 118248 KB Output is correct
22 Correct 57 ms 118712 KB Output is correct
23 Correct 57 ms 118860 KB Output is correct
24 Incorrect 74 ms 118512 KB Output isn't correct
25 Halted 0 ms 0 KB -