oj.uz

Submission #15591

# Submission time Handle Problem Language Result Execution time Memory
15591 2015-07-13T04:01:39 Z gs14004 Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 82760 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;
                ret = disj.size[df];
            }
            else{
                return 0;
            }
        }
        vis[df] = 1;
    }
    if(get_strange == -1) return n;
    if(ret) return ret;
    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;*/
}

/*
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

void Init(int N);
int CountCritical();
void Link(int a, int b);

int main() {
  int tmp;

  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);

  int N, L;
  tmp = scanf("%d %d", &N, &L);
  assert(tmp == 2);
  Init(N);

  int i;
  for (i = 0; i < L; i++) {
    int A, B;
    tmp = scanf("%d", &A);
    if (A == -1) {
      int critical;
      critical = CountCritical();
      printf("%d\n", critical);
    } else {
      tmp = scanf("%d", &B);
      assert(tmp == 1);
      Link(A, B);
    }
  }

  return 0;

}*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24824 KB Output is correct
2 Correct 38 ms 26236 KB Output is correct
3 Correct 391 ms 26380 KB Output is correct
4 Correct 22 ms 26380 KB Output is correct
5 Correct 26 ms 26380 KB Output is correct
6 Correct 25 ms 26380 KB Output is correct
7 Correct 24 ms 26380 KB Output is correct
8 Correct 24 ms 26380 KB Output is correct
9 Correct 385 ms 26576 KB Output is correct
10 Correct 90 ms 26576 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 61776 KB Output is correct
2 Execution timed out 4053 ms 82760 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24824 KB Output is correct
2 Correct 38 ms 26236 KB Output is correct
3 Correct 391 ms 26380 KB Output is correct
4 Correct 22 ms 26380 KB Output is correct
5 Correct 26 ms 26380 KB Output is correct
6 Correct 25 ms 26380 KB Output is correct
7 Correct 24 ms 26380 KB Output is correct
8 Correct 24 ms 26380 KB Output is correct
9 Correct 385 ms 26576 KB Output is correct
10 Correct 90 ms 26576 KB Output is correct
11 Correct 51 ms 82760 KB Output is correct
12 Execution timed out 4042 ms 82760 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24824 KB Output is correct
2 Correct 38 ms 26236 KB Output is correct
3 Correct 391 ms 26380 KB Output is correct
4 Correct 22 ms 26380 KB Output is correct
5 Correct 26 ms 26380 KB Output is correct
6 Correct 25 ms 26380 KB Output is correct
7 Correct 24 ms 26380 KB Output is correct
8 Correct 24 ms 26380 KB Output is correct
9 Correct 385 ms 26576 KB Output is correct
10 Correct 90 ms 26576 KB Output is correct
11 Correct 51 ms 82760 KB Output is correct
12 Execution timed out 4042 ms 82760 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24824 KB Output is correct
2 Correct 38 ms 26236 KB Output is correct
3 Correct 391 ms 26380 KB Output is correct
4 Correct 22 ms 26380 KB Output is correct
5 Correct 26 ms 26380 KB Output is correct
6 Correct 25 ms 26380 KB Output is correct
7 Correct 24 ms 26380 KB Output is correct
8 Correct 24 ms 26380 KB Output is correct
9 Correct 385 ms 26576 KB Output is correct
10 Correct 90 ms 26576 KB Output is correct
11 Correct 659 ms 61776 KB Output is correct
12 Execution timed out 4053 ms 82760 KB Time limit exceeded
13 Halted 0 ms 0 KB -