oj.uz

Submission #1035535

# Submission time Handle Problem Language Result Execution time Memory
1035535 2024-07-26T11:46:35 Z Warinchai Parachute rings (IOI12_rings) C++14
37 / 100
 1829 ms 250820 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])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 69 ms 117664 KB Output is correct
2 Correct 51 ms 118204 KB Output is correct
3 Correct 47 ms 118352 KB Output is correct
4 Correct 51 ms 117840 KB Output is correct
5 Correct 61 ms 118104 KB Output is correct
6 Correct 67 ms 118580 KB Output is correct
7 Correct 49 ms 118100 KB Output is correct
8 Correct 50 ms 118100 KB Output is correct
9 Correct 78 ms 118352 KB Output is correct
10 Correct 53 ms 118356 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 168020 KB Output is correct
2 Correct 757 ms 195036 KB Output is correct
3 Correct 366 ms 183124 KB Output is correct
4 Correct 986 ms 219108 KB Output is correct
5 Correct 1080 ms 227208 KB Output is correct
6 Correct 1829 ms 250820 KB Output is correct
7 Correct 362 ms 182836 KB Output is correct
8 Correct 821 ms 208364 KB Output is correct
9 Correct 898 ms 214280 KB Output is correct
10 Correct 893 ms 217324 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 117664 KB Output is correct
2 Correct 51 ms 118204 KB Output is correct
3 Correct 47 ms 118352 KB Output is correct
4 Correct 51 ms 117840 KB Output is correct
5 Correct 61 ms 118104 KB Output is correct
6 Correct 67 ms 118580 KB Output is correct
7 Correct 49 ms 118100 KB Output is correct
8 Correct 50 ms 118100 KB Output is correct
9 Correct 78 ms 118352 KB Output is correct
10 Correct 53 ms 118356 KB Output is correct
11 Correct 53 ms 118348 KB Output is correct
12 Correct 59 ms 118864 KB Output is correct
13 Correct 57 ms 118864 KB Output is correct
14 Incorrect 77 ms 118572 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 117664 KB Output is correct
2 Correct 51 ms 118204 KB Output is correct
3 Correct 47 ms 118352 KB Output is correct
4 Correct 51 ms 117840 KB Output is correct
5 Correct 61 ms 118104 KB Output is correct
6 Correct 67 ms 118580 KB Output is correct
7 Correct 49 ms 118100 KB Output is correct
8 Correct 50 ms 118100 KB Output is correct
9 Correct 78 ms 118352 KB Output is correct
10 Correct 53 ms 118356 KB Output is correct
11 Correct 53 ms 118348 KB Output is correct
12 Correct 59 ms 118864 KB Output is correct
13 Correct 57 ms 118864 KB Output is correct
14 Incorrect 77 ms 118572 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 117664 KB Output is correct
2 Correct 51 ms 118204 KB Output is correct
3 Correct 47 ms 118352 KB Output is correct
4 Correct 51 ms 117840 KB Output is correct
5 Correct 61 ms 118104 KB Output is correct
6 Correct 67 ms 118580 KB Output is correct
7 Correct 49 ms 118100 KB Output is correct
8 Correct 50 ms 118100 KB Output is correct
9 Correct 78 ms 118352 KB Output is correct
10 Correct 53 ms 118356 KB Output is correct
11 Correct 459 ms 168020 KB Output is correct
12 Correct 757 ms 195036 KB Output is correct
13 Correct 366 ms 183124 KB Output is correct
14 Correct 986 ms 219108 KB Output is correct
15 Correct 1080 ms 227208 KB Output is correct
16 Correct 1829 ms 250820 KB Output is correct
17 Correct 362 ms 182836 KB Output is correct
18 Correct 821 ms 208364 KB Output is correct
19 Correct 898 ms 214280 KB Output is correct
20 Correct 893 ms 217324 KB Output is correct
21 Correct 53 ms 118348 KB Output is correct
22 Correct 59 ms 118864 KB Output is correct
23 Correct 57 ms 118864 KB Output is correct
24 Incorrect 77 ms 118572 KB Output isn't correct
25 Halted 0 ms 0 KB -