oj.uz

Submission #1035490

# Submission time Handle Problem Language Result Execution time Memory
1035490 2024-07-26T11:32:56 Z Warinchai Parachute rings (IOI12_rings) C++14
20 / 100
 395 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
int N;
set<int>s[4000005];
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 100 ms 213504 KB Output is correct
2 Correct 101 ms 213840 KB Output is correct
3 Correct 97 ms 214100 KB Output is correct
4 Correct 96 ms 213632 KB Output is correct
5 Correct 96 ms 213912 KB Output is correct
6 Correct 97 ms 214352 KB Output is correct
7 Correct 97 ms 213844 KB Output is correct
8 Correct 96 ms 214096 KB Output is correct
9 Correct 97 ms 214104 KB Output is correct
10 Correct 99 ms 214052 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 262144 KB Output is correct
2 Runtime error 292 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 213504 KB Output is correct
2 Correct 101 ms 213840 KB Output is correct
3 Correct 97 ms 214100 KB Output is correct
4 Correct 96 ms 213632 KB Output is correct
5 Correct 96 ms 213912 KB Output is correct
6 Correct 97 ms 214352 KB Output is correct
7 Correct 97 ms 213844 KB Output is correct
8 Correct 96 ms 214096 KB Output is correct
9 Correct 97 ms 214104 KB Output is correct
10 Correct 99 ms 214052 KB Output is correct
11 Correct 98 ms 214096 KB Output is correct
12 Correct 101 ms 214608 KB Output is correct
13 Correct 102 ms 214620 KB Output is correct
14 Incorrect 98 ms 214500 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 213504 KB Output is correct
2 Correct 101 ms 213840 KB Output is correct
3 Correct 97 ms 214100 KB Output is correct
4 Correct 96 ms 213632 KB Output is correct
5 Correct 96 ms 213912 KB Output is correct
6 Correct 97 ms 214352 KB Output is correct
7 Correct 97 ms 213844 KB Output is correct
8 Correct 96 ms 214096 KB Output is correct
9 Correct 97 ms 214104 KB Output is correct
10 Correct 99 ms 214052 KB Output is correct
11 Correct 98 ms 214096 KB Output is correct
12 Correct 101 ms 214608 KB Output is correct
13 Correct 102 ms 214620 KB Output is correct
14 Incorrect 98 ms 214500 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 213504 KB Output is correct
2 Correct 101 ms 213840 KB Output is correct
3 Correct 97 ms 214100 KB Output is correct
4 Correct 96 ms 213632 KB Output is correct
5 Correct 96 ms 213912 KB Output is correct
6 Correct 97 ms 214352 KB Output is correct
7 Correct 97 ms 213844 KB Output is correct
8 Correct 96 ms 214096 KB Output is correct
9 Correct 97 ms 214104 KB Output is correct
10 Correct 99 ms 214052 KB Output is correct
11 Correct 395 ms 262144 KB Output is correct
12 Runtime error 292 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -