Submission #15593

#	Time	Username	Problem	Language	Result	Execution time	Memory
15593		gs14004	Parachute rings (IOI12_rings)	C++14	55 / 100	4032 ms	96380 KiB

rings

#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];
 
    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];
        repres4[p] = max(repres4[p], repres4[q]);
        repres3[p] = max(repres3[p], repres3[q]);
    }
}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;
    if(disj.degcnt[get_strange][4] == 1){
        return solve(disj.repres4[get_strange]);
    }
    int p = disj.repres3[get_strange];
    ret = solve(p);
    for(auto &i : graph[p]){
        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 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31