Submission #233348

#	Time	Username	Problem	Language	Result	Execution time	Memory
233348		Mercenary	Parachute rings (IOI12_rings)	C++14	100 / 100	710 ms	41592 KiB

rings

#include<bits/stdc++.h>

using namespace std;
#define taskname "A"
#define pb	push_back
#define mp  make_pair
typedef pair<int,int> ii;

typedef long double ld;
typedef long long ll;

const int maxn = 1e6 + 5;

int adj[maxn][2];

int n;

struct G{
    bitset<maxn> is_link;
    int lab[maxn];
    int banned = -1;
    bool ok = 1;
    void init(int u){
        banned = u;
        for(int i = 0 ; i < n ; ++i)lab[i] = -1;
        for(int i = 0 ; i < n ; ++i){
            for(int j = 0 ; j < 2 ; ++j){
                if(adj[i][j] != -1 && i > adj[i][j]){
                    Connect(i,adj[i][j]);
                }
            }
        }
    }
    int FindLab(int u){return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);}
    void Connect(int u , int v){
        if(ok == 0 && banned != -1)return;
        if(u == banned)is_link[v] = 1;
        if(v == banned)is_link[u] = 1;
        if(u == banned || v == banned)return;
        u = FindLab(u);v = FindLab(v);
        if(u == v){
            ok = 0;
            return;
        }
        if(lab[u] > lab[v])swap(u , v);
        lab[u] += lab[v];
        lab[v] = u;
    }

}a[4];

void Init(int _n){
    memset(adj,-1,sizeof adj);
    n = _n;
    for(int i = 0 ; i < n ; ++i)a[0].lab[i] = -1;
}

int cycle = 0;
int CurState = 0;

int dfs(int u , int b){
    int res = 1;
    int par = b;
    while(u != b){
        res++;
        for(int i = 0 ; i < 2 ; ++i){
            if(adj[u][i] != -1 && adj[u][i] != par){
                par = u;u = adj[u][i];
                break;
            }
        }
    }
    return res;
}

int deg[maxn];

void Link(int a , int b){
    if(CurState == 4)return;
    if(deg[a] < deg[b])swap(a,b);
    deg[a]++;deg[b]++;
    if(CurState == 3){
        for(int i = 0 ; i < 4 ; ++i){
            ::a[i].Connect(a,b);
            if((a != ::a[i].banned && deg[a] - ::a[i].is_link[a] > 2) ||
               (b != ::a[i].banned && deg[b] - ::a[i].is_link[b] > 2))::a[i].ok = 0;
        }
        return;
    }
    if(deg[a] == 3){
        CurState = 3;
        for(int i = 0 ; i < 2 ; ++i){
            ::a[i].init(adj[a][i]);
        }
        ::a[2].init(b);
        ::a[3].init(a);
        for(int i = 0 ; i < 4 ; ++i){
            ::a[i].Connect(a,b);
            if((a != ::a[i].banned && deg[a] - ::a[i].is_link[a] > 2) ||
               (b != ::a[i].banned && deg[b] - ::a[i].is_link[b] > 2)){
                    ::a[i].ok = 0;
//                    cout << ::a[i].banned << endl;
               }
        }
        return;
    }
    for(int i = 0 ; i < 2 ; ++i){
        if(adj[a][i] == -1){
            adj[a][i] = b;
            break;
        }
    }
    for(int i = 0 ; i < 2 ; ++i){
        if(adj[b][i] == -1){
            adj[b][i] = a;
            break;
        }
    }
    if(::a[0].FindLab(a) == ::a[0].FindLab(b)){
        if(CurState == 2)CurState = 4;
        else cycle = dfs(a , b) , CurState = 2;
    }else{
         ::a[0].Connect(a , b);
    }

}

int CountCritical(){
    if(CurState == 4)return 0;
    if(CurState == 3){
        int res = 0;
        for(int i = 0 ; i < 4 ; ++i){
            res += a[i].ok;
        }
        if(res == 0)CurState = 4;
        return res;
    }
//    cout << CurState << endl;
    if(CurState == 2)return cycle;
    return n;
}

#ifdef LOCAL

#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() {
    freopen("A.INP","r",stdin);
  int tmp;
  /* Set input and output buffering */
  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;

}
#endif // LOCAL

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31