oj.uz

답안 #1035564

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1035564 2024-07-26T11:57:01 Z Warinchai 낙하산 고리들 (IOI12_rings) C++14
20 / 100
 1630 ms 262144 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);}
map<pair<int,int>,int>mp;
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(mp[{A,B}]||mp[{B,A}])return;
    mp[{A,B}]++;mp[{B,A}]++;
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 117776 KB Output is correct
2 Correct 50 ms 118608 KB Output is correct
3 Correct 58 ms 118868 KB Output is correct
4 Correct 53 ms 118100 KB Output is correct
5 Correct 57 ms 118612 KB Output is correct
6 Correct 58 ms 119076 KB Output is correct
7 Correct 59 ms 118152 KB Output is correct
8 Correct 57 ms 118616 KB Output is correct
9 Correct 58 ms 118964 KB Output is correct
10 Correct 59 ms 118876 KB Output is correct

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1279 ms 234320 KB Output is correct
2 Runtime error 1630 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 117776 KB Output is correct
2 Correct 50 ms 118608 KB Output is correct
3 Correct 58 ms 118868 KB Output is correct
4 Correct 53 ms 118100 KB Output is correct
5 Correct 57 ms 118612 KB Output is correct
6 Correct 58 ms 119076 KB Output is correct
7 Correct 59 ms 118152 KB Output is correct
8 Correct 57 ms 118616 KB Output is correct
9 Correct 58 ms 118964 KB Output is correct
10 Correct 59 ms 118876 KB Output is correct
11 Correct 58 ms 118864 KB Output is correct
12 Correct 65 ms 120148 KB Output is correct
13 Correct 65 ms 120180 KB Output is correct
14 Incorrect 62 ms 119380 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 117776 KB Output is correct
2 Correct 50 ms 118608 KB Output is correct
3 Correct 58 ms 118868 KB Output is correct
4 Correct 53 ms 118100 KB Output is correct
5 Correct 57 ms 118612 KB Output is correct
6 Correct 58 ms 119076 KB Output is correct
7 Correct 59 ms 118152 KB Output is correct
8 Correct 57 ms 118616 KB Output is correct
9 Correct 58 ms 118964 KB Output is correct
10 Correct 59 ms 118876 KB Output is correct
11 Correct 58 ms 118864 KB Output is correct
12 Correct 65 ms 120148 KB Output is correct
13 Correct 65 ms 120180 KB Output is correct
14 Incorrect 62 ms 119380 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 117776 KB Output is correct
2 Correct 50 ms 118608 KB Output is correct
3 Correct 58 ms 118868 KB Output is correct
4 Correct 53 ms 118100 KB Output is correct
5 Correct 57 ms 118612 KB Output is correct
6 Correct 58 ms 119076 KB Output is correct
7 Correct 59 ms 118152 KB Output is correct
8 Correct 57 ms 118616 KB Output is correct
9 Correct 58 ms 118964 KB Output is correct
10 Correct 59 ms 118876 KB Output is correct
11 Correct 1279 ms 234320 KB Output is correct
12 Runtime error 1630 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -