oj.uz

Submission #15590

# Submission time Handle Problem Language Result Execution time Memory
15590 2015-07-13T03:59:35 Z gs14004 Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 82880 KB 
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
 
vector<int> graph[1000005];
int n;
 
struct disj{
    int pa[1000005];
    int degcnt[1000005][5];
    int repres3[1000005];
    int repres4[1000005];
    int cnt[1000005];
    int size[1000005];
 
    bool trash[1000005];
    bool bad[1000005];
    bool cycle[1000005];
 
    void init(int n){
        for(int i=0; i<=n; i++) pa[i] = i, degcnt[i][0] = 1, size[i] = 1, repres3[i] = repres4[i] = -1;
    }
 
    int find(int x){
        return pa[x] = (pa[x] == x ? x : find(pa[x]));
    }
 
    void uni(int p, int q){
        p = find(p); q = find(q);
        if(p == q) return;
        pa[q] = p; find(q);
        for(int i=0; i<5; i++){
            degcnt[p][i] += degcnt[q][i];
        }
        size[p] += size[q];
        if(degcnt[p][4] > 1){
            trash[p] = 1;
            bad[p] = 0;
            cycle[p] = 0;
            return;
        }
        else{
            repres4[p] = max(repres4[p], repres4[q]);
            repres3[p] = max(repres3[p], repres3[q]);
        }
        if(degcnt[p][3] || degcnt[p][4]){
            bad[p] = 1;
            cycle[p] = 0;
        }
        else if(degcnt[p][1] == 0){
            cycle[p] = 1;
        }
    }
}disj;
 
void Init(int N){
    n = N; 
    disj.init(n);
}
 
int deg[1000005];
 
void Link(int A, int B){
    graph[A].push_back(B);
    graph[B].push_back(A);
    deg[A]++, deg[B]++;
    int p = disj.find(A);
    if(deg[A] <= 4){
        disj.degcnt[p][deg[A]-1]--;
        disj.degcnt[p][deg[A]]++;
        if(deg[A] == 3) disj.repres3[p] = A;
        if(deg[A] == 4) disj.repres4[p] = A;
    }
    p = disj.find(B);
    if(deg[B] <= 4){
        disj.degcnt[p][deg[B]-1]--;
        disj.degcnt[p][deg[B]]++;
        if(deg[B] == 3) disj.repres3[p] = B;
        if(deg[B] == 4) disj.repres4[p] = B;
    }
    disj.uni(A,B);
}
 
bool vis[1000005];
queue<int> q;
 
bool tvis[1000005];
 
int solve(int x){
    memset(tvis,0,sizeof(tvis));
    tvis[x] = 1;
    int ret = 1;
    for(auto &i : graph[x]){
        deg[x]--;
        deg[i]--;
    }
    for(auto &i : graph[x]){
        if(tvis[i]) continue;
        tvis[i] = 1;
        q.push(i);
        int foundThree = 0, foundOne = 0, foundTwo = 0;
        while(!q.empty()){
            int qf = q.front();
            q.pop();
            if(deg[qf] >= 3) foundThree = 1;
            if(deg[qf] == 1) foundOne = 1;
            if(deg[qf] == 2) foundTwo = 1;
            for(auto &i : graph[qf]){
                if(!tvis[i]){
                    tvis[i] = 1;
                    q.push(i);
                }
            }
        }
        if(foundThree == 1){
            ret = 0;
            break;
        }
        if(foundTwo && !foundOne){
            ret = 0;
            break;
        }
    }
    for(auto &i : graph[x]){
        deg[x]++;
        deg[i]++;
    }
    return ret;
}
 
int CountCritical(){
    memset(vis,0,sizeof(vis));
    int ret = 0;
    int get_strange = -1;
    for(int i=0; i<n; i++){
        int df = disj.find(i);
        if(vis[df]) continue;
        if(disj.degcnt[df][3] || disj.degcnt[df][4]){
            if(get_strange == -1){
                get_strange = df;
            }
            else{
                return 0;
            }
        }
        else if(disj.degcnt[df][2] && !disj.degcnt[df][1]){
            if(get_strange == -1){
                get_strange = df;
            }
            else{
                return 0;
            }
        }
        vis[df] = 1;
    }
    if(get_strange == -1) return n;
    for(int i=0; i<n; i++){
        if(disj.find(i) == get_strange){
            if(solve(i)) ret++;
        }
    }
    return ret;/*
    memset(vis,0,sizeof(vis));
    int ret = 0, pos = -1;
    for(int i=0; i<n; i++){
        int p = disj.find(i);
        if(vis[p]) continue;
        vis[p] = 1;
        if(disj.trash[p]) return 0;
        else if(disj.cycle[p]){
            if(~pos) return 0;
            pos = p;
            ret = disj.size[p];
        }
        else if(disj.bad[p]){
            if(~pos) return 0;
            pos = p;
            ret = -1;
        }
        else{
            if(pos == -1) ret += disj.size[p];
        }
    }
    if(ret == -1){
        if(~disj.repres4[pos]){
            ret = 0;
            pos = disj.repres4[pos];
            return solve(pos);
        }
        else{
            ret = 0;
            pos = disj.repres3[pos];
            if(solve(pos)) ret++;
            for(auto &k : graph[pos]){
                if(solve(k)) ret++;
            }
        }
    }
    return ret;*/
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24824 KB Output is correct
2 Correct 39 ms 26236 KB Output is correct
3 Correct 399 ms 26408 KB Output is correct
4 Correct 29 ms 26408 KB Output is correct
5 Correct 180 ms 26408 KB Output is correct
6 Correct 601 ms 26408 KB Output is correct
7 Correct 24 ms 26408 KB Output is correct
8 Correct 26 ms 26408 KB Output is correct
9 Correct 398 ms 26484 KB Output is correct
10 Correct 78 ms 26484 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 61728 KB Output is correct
2 Execution timed out 4049 ms 82880 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24824 KB Output is correct
2 Correct 39 ms 26236 KB Output is correct
3 Correct 399 ms 26408 KB Output is correct
4 Correct 29 ms 26408 KB Output is correct
5 Correct 180 ms 26408 KB Output is correct
6 Correct 601 ms 26408 KB Output is correct
7 Correct 24 ms 26408 KB Output is correct
8 Correct 26 ms 26408 KB Output is correct
9 Correct 398 ms 26484 KB Output is correct
10 Correct 78 ms 26484 KB Output is correct
11 Correct 54 ms 82880 KB Output is correct
12 Execution timed out 4035 ms 82880 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24824 KB Output is correct
2 Correct 39 ms 26236 KB Output is correct
3 Correct 399 ms 26408 KB Output is correct
4 Correct 29 ms 26408 KB Output is correct
5 Correct 180 ms 26408 KB Output is correct
6 Correct 601 ms 26408 KB Output is correct
7 Correct 24 ms 26408 KB Output is correct
8 Correct 26 ms 26408 KB Output is correct
9 Correct 398 ms 26484 KB Output is correct
10 Correct 78 ms 26484 KB Output is correct
11 Correct 54 ms 82880 KB Output is correct
12 Execution timed out 4035 ms 82880 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24824 KB Output is correct
2 Correct 39 ms 26236 KB Output is correct
3 Correct 399 ms 26408 KB Output is correct
4 Correct 29 ms 26408 KB Output is correct
5 Correct 180 ms 26408 KB Output is correct
6 Correct 601 ms 26408 KB Output is correct
7 Correct 24 ms 26408 KB Output is correct
8 Correct 26 ms 26408 KB Output is correct
9 Correct 398 ms 26484 KB Output is correct
10 Correct 78 ms 26484 KB Output is correct
11 Correct 681 ms 61728 KB Output is correct
12 Execution timed out 4049 ms 82880 KB Time limit exceeded
13 Halted 0 ms 0 KB -