oj.uz

Submission #1035584

# Submission time Handle Problem Language Result Execution time Memory
1035584 2024-07-26T12:08:48 Z Warinchai Parachute rings (IOI12_rings) C++14
37 / 100
 1741 ms 253892 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(vis[A])dfs(A,from[A]);
    if(vis[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 49 ms 117840 KB Output is correct
2 Correct 67 ms 118100 KB Output is correct
3 Correct 49 ms 118356 KB Output is correct
4 Correct 55 ms 117992 KB Output is correct
5 Correct 57 ms 118096 KB Output is correct
6 Correct 71 ms 118624 KB Output is correct
7 Correct 56 ms 117948 KB Output is correct
8 Correct 53 ms 118100 KB Output is correct
9 Correct 47 ms 118356 KB Output is correct
10 Correct 68 ms 118356 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 171344 KB Output is correct
2 Correct 845 ms 200536 KB Output is correct
3 Correct 403 ms 189644 KB Output is correct
4 Correct 959 ms 224196 KB Output is correct
5 Correct 1028 ms 230004 KB Output is correct
6 Correct 1741 ms 253892 KB Output is correct
7 Correct 354 ms 189268 KB Output is correct
8 Correct 686 ms 214352 KB Output is correct
9 Correct 737 ms 221200 KB Output is correct
10 Correct 649 ms 222032 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 117840 KB Output is correct
2 Correct 67 ms 118100 KB Output is correct
3 Correct 49 ms 118356 KB Output is correct
4 Correct 55 ms 117992 KB Output is correct
5 Correct 57 ms 118096 KB Output is correct
6 Correct 71 ms 118624 KB Output is correct
7 Correct 56 ms 117948 KB Output is correct
8 Correct 53 ms 118100 KB Output is correct
9 Correct 47 ms 118356 KB Output is correct
10 Correct 68 ms 118356 KB Output is correct
11 Correct 57 ms 118352 KB Output is correct
12 Correct 58 ms 118976 KB Output is correct
13 Correct 59 ms 118888 KB Output is correct
14 Incorrect 58 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 49 ms 117840 KB Output is correct
2 Correct 67 ms 118100 KB Output is correct
3 Correct 49 ms 118356 KB Output is correct
4 Correct 55 ms 117992 KB Output is correct
5 Correct 57 ms 118096 KB Output is correct
6 Correct 71 ms 118624 KB Output is correct
7 Correct 56 ms 117948 KB Output is correct
8 Correct 53 ms 118100 KB Output is correct
9 Correct 47 ms 118356 KB Output is correct
10 Correct 68 ms 118356 KB Output is correct
11 Correct 57 ms 118352 KB Output is correct
12 Correct 58 ms 118976 KB Output is correct
13 Correct 59 ms 118888 KB Output is correct
14 Incorrect 58 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 49 ms 117840 KB Output is correct
2 Correct 67 ms 118100 KB Output is correct
3 Correct 49 ms 118356 KB Output is correct
4 Correct 55 ms 117992 KB Output is correct
5 Correct 57 ms 118096 KB Output is correct
6 Correct 71 ms 118624 KB Output is correct
7 Correct 56 ms 117948 KB Output is correct
8 Correct 53 ms 118100 KB Output is correct
9 Correct 47 ms 118356 KB Output is correct
10 Correct 68 ms 118356 KB Output is correct
11 Correct 465 ms 171344 KB Output is correct
12 Correct 845 ms 200536 KB Output is correct
13 Correct 403 ms 189644 KB Output is correct
14 Correct 959 ms 224196 KB Output is correct
15 Correct 1028 ms 230004 KB Output is correct
16 Correct 1741 ms 253892 KB Output is correct
17 Correct 354 ms 189268 KB Output is correct
18 Correct 686 ms 214352 KB Output is correct
19 Correct 737 ms 221200 KB Output is correct
20 Correct 649 ms 222032 KB Output is correct
21 Correct 57 ms 118352 KB Output is correct
22 Correct 58 ms 118976 KB Output is correct
23 Correct 59 ms 118888 KB Output is correct
24 Incorrect 58 ms 118608 KB Output isn't correct
25 Halted 0 ms 0 KB -