oj.uz

Submission #1035507

# Submission time Handle Problem Language Result Execution time Memory
1035507 2024-07-26T11:38:23 Z Warinchai Parachute rings (IOI12_rings) C++14
37 / 100
 1514 ms 253912 KB 
#include<bits/stdc++.h>
using namespace std;
int N;
set<int>s[2000005];
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 61 ms 117840 KB Output is correct
2 Correct 54 ms 118296 KB Output is correct
3 Correct 51 ms 118352 KB Output is correct
4 Correct 65 ms 117844 KB Output is correct
5 Correct 55 ms 118100 KB Output is correct
6 Correct 56 ms 118608 KB Output is correct
7 Correct 51 ms 118100 KB Output is correct
8 Correct 57 ms 118340 KB Output is correct
9 Correct 53 ms 118352 KB Output is correct
10 Correct 56 ms 118352 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 169556 KB Output is correct
2 Correct 577 ms 197204 KB Output is correct
3 Correct 368 ms 185688 KB Output is correct
4 Correct 781 ms 221944 KB Output is correct
5 Correct 814 ms 230172 KB Output is correct
6 Correct 1514 ms 253912 KB Output is correct
7 Correct 387 ms 185172 KB Output is correct
8 Correct 742 ms 211028 KB Output is correct
9 Correct 818 ms 217172 KB Output is correct
10 Correct 591 ms 219988 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 117840 KB Output is correct
2 Correct 54 ms 118296 KB Output is correct
3 Correct 51 ms 118352 KB Output is correct
4 Correct 65 ms 117844 KB Output is correct
5 Correct 55 ms 118100 KB Output is correct
6 Correct 56 ms 118608 KB Output is correct
7 Correct 51 ms 118100 KB Output is correct
8 Correct 57 ms 118340 KB Output is correct
9 Correct 53 ms 118352 KB Output is correct
10 Correct 56 ms 118352 KB Output is correct
11 Correct 52 ms 118356 KB Output is correct
12 Correct 56 ms 118836 KB Output is correct
13 Correct 58 ms 118864 KB Output is correct
14 Incorrect 54 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 61 ms 117840 KB Output is correct
2 Correct 54 ms 118296 KB Output is correct
3 Correct 51 ms 118352 KB Output is correct
4 Correct 65 ms 117844 KB Output is correct
5 Correct 55 ms 118100 KB Output is correct
6 Correct 56 ms 118608 KB Output is correct
7 Correct 51 ms 118100 KB Output is correct
8 Correct 57 ms 118340 KB Output is correct
9 Correct 53 ms 118352 KB Output is correct
10 Correct 56 ms 118352 KB Output is correct
11 Correct 52 ms 118356 KB Output is correct
12 Correct 56 ms 118836 KB Output is correct
13 Correct 58 ms 118864 KB Output is correct
14 Incorrect 54 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 61 ms 117840 KB Output is correct
2 Correct 54 ms 118296 KB Output is correct
3 Correct 51 ms 118352 KB Output is correct
4 Correct 65 ms 117844 KB Output is correct
5 Correct 55 ms 118100 KB Output is correct
6 Correct 56 ms 118608 KB Output is correct
7 Correct 51 ms 118100 KB Output is correct
8 Correct 57 ms 118340 KB Output is correct
9 Correct 53 ms 118352 KB Output is correct
10 Correct 56 ms 118352 KB Output is correct
11 Correct 348 ms 169556 KB Output is correct
12 Correct 577 ms 197204 KB Output is correct
13 Correct 368 ms 185688 KB Output is correct
14 Correct 781 ms 221944 KB Output is correct
15 Correct 814 ms 230172 KB Output is correct
16 Correct 1514 ms 253912 KB Output is correct
17 Correct 387 ms 185172 KB Output is correct
18 Correct 742 ms 211028 KB Output is correct
19 Correct 818 ms 217172 KB Output is correct
20 Correct 591 ms 219988 KB Output is correct
21 Correct 52 ms 118356 KB Output is correct
22 Correct 56 ms 118836 KB Output is correct
23 Correct 58 ms 118864 KB Output is correct
24 Incorrect 54 ms 118608 KB Output isn't correct
25 Halted 0 ms 0 KB -