Submission #107684

#	Time	Username	Problem	Language	Result	Execution time	Memory
107684		MrTEK	Parachute rings (IOI12_rings)	C++14	100 / 100	2842 ms	121300 KiB

rings

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int dad[N][5],ans[5],deg[N][5],lst[5],wh[5],vis[N];
int n,m,cnt;
vector <int> ed[N];
pair <int,int> edge[N];
bool flag = 0;
 
int find(int u,int x) {
  if (dad[u][x] == u)
    return dad[u][x];
  return dad[u][x] = find(dad[u][x],x);
}
 
bool merge(int u,int v,int x) {
  int du = find(u,x);
  int dv = find(v,x);
  if (du == dv)
    return false;
  dad[du][x] = dv;
  return true;
}
 
void dfs(int cur) {
  if (vis[cur])
    return;
  vis[cur] = 1;
  cnt++;
  for (auto i : ed[cur])
    dfs(i);
}
 
int get(int cur) {
  cnt = 0;
  dfs(cur);
  return cnt;
}
 
void Init(int N_) {
  n = N_;
  for (int i = 0 ; i < 5 ; i++) {
    ans[i] = 1;
    lst[i] = 1;
    for (int j = 1 ; j <= n ; j++) {
      dad[j][i] = j;
      deg[j][i] = 0;
    }
  }
  ans[0] = n;
}
 
void Link(int A, int B) {
  A++ , B++;
  deg[A][0]++;
  deg[B][0]++;
  ed[A].push_back(B);
  ed[B].push_back(A);
  edge[++m] = {A,B};
  if (flag)
    return;
  if (deg[A][0] == 3) {
    int t = 1;
    wh[1] =  A;
    for (auto i : ed[A])
      wh[++t] = i;
    flag = true;
  }
  else if (deg[B][0] == 3) {
    int t = 1;
    wh[1] =  B;
    for (auto i : ed[B])
      wh[++t] = i;
    flag = true;
  }
  else if (merge(A,B,0) == false)
    ans[0] != n ? ans[0] = 0 : ans[0] = get(A);
}
 
int CountCritical() {
  if (flag == false)
    return ans[0];
  int res = 0;
  for  (int i = 1 ; i < 5 ; i++) {
    if (ans[i] == 0)
      continue;
    for ( ; lst[i] <= m ; lst[i]++) {
      int u = edge[lst[i]].first;
      int v = edge[lst[i]].second;
      if (u == wh[i] || v == wh[i])
        continue;
      deg[u][i]++;
      deg[v][i]++;
      if (deg[u][i] == 3 || deg[v][i] == 3 || merge(u,v,i) == false)
        ans[i] = 0;
    }
    res += ans[i];
  }
  return res;
}

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