Submission #64212

#	Time	Username	Problem	Language	Result	Execution time	Memory
64212		chpipis	Parachute rings (IOI12_rings)	C++11	55 / 100	4027 ms	76088 KiB

rings

#if 0

#include <bits/stdc++.h>
using namespace std;
 
//#define TEST
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
 
const int len = 1e6;
int n, state, cycle, last, t;
int par[4][len], deg[4][len], sz[4][len], block[4][len], fine[4];
vector<int> adj[len];
vector<ii> edge;
 
int fin(int i){
    if (par[t][i] == i) return i;
    return par[t][i] = fin(par[t][i]);
}
 
void join(int i, int j){
    i = fin(i), j = fin(j);
    if (i == j) return;
 
    if (sz[t][i] > sz[t][j])
        sz[t][i] += sz[t][j], par[t][j] = i;
    else
        sz[t][j] += sz[t][i], par[t][i] = j;
}
 
void build(int u){
    block[t][u] = 1;
    for (int i = 0; i < n; i++)
        par[t][i] = i, deg[t][i] = 0, sz[t][i] = 1;
 
    fine[t] = 1;
    for (int i = 0; i < edge.size(); i++){
        int a = edge[i].fi, b = edge[i].se;
        if (!fine[t] || block[t][a] || block[t][b]) continue;
 
        if (deg[t][a] > 1 || deg[t][b] > 1 || fin(a) == fin(b))
            fine[t] = 0;
        deg[t][a]++, deg[t][b]++;
        join(a, b);
    }
}
 
void Init(int N){
    n = N, state = 0, cycle = 0, last = 0, t = 0;
 
    for (int i = 0; i < n; i++)
        par[0][i] = i, deg[0][i] = 0, sz[0][i] = 1;
}
 
void Link(int a, int b){
    edge.pb(mp(a, b));
    if (state == 0){
        adj[a].pb(b), adj[b].pb(a);
        deg[0][a]++, deg[0][b]++;
 
        if (deg[0][a] < deg[0][b])
            swap(a, b);
 
        if (deg[0][a] == 3){
            state = 1;
            t = 0, build(a);
            t = 1, build(adj[a][0]);
            t = 2, build(adj[a][1]);
            t = 3, build(adj[a][2]);
        }
        else{
            a = fin(a), b = fin(b);
            if (a == b)
                cycle++, last = sz[0][a];
            else
                join(a, b);
        }
    }
    else{
        for (t = 0; t < 4; t++){
            if (!fine[t] || block[t][a] || block[t][b]) continue;
 
            if (deg[t][a] > 1 || deg[t][b] > 1 || fin(a) == fin(b))
                fine[t] = 0;
            deg[t][a]++, deg[t][b]++;
            join(a, b);
        }
    }
}
 
int CountCritical(){
    int ans = 0;
    if (state == 0){
        if (cycle == 0) ans = n;
        else if (cycle == 1) ans = last;
        else ans = 0;
    }
    else{
        for (int j = 0; j < 4; j++)
            ans += fine[j];
    }
 
    return ans;
}
 
#ifdef TEST
int main() {
  freopen("example.txt", "r", stdin);
  int tmp;
 
  /* Set input and output buffering */
  char *inbuf, *outbuf;
  inbuf = (char*) malloc((1 << 16) * sizeof(char));
  outbuf = (char*) malloc((1 << 16) * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, (1 << 16));
  tmp = setvbuf(stdout, outbuf, _IOFBF, (1 << 16));
 
  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 // TEST

#else

#ifndef EVAL
#include "grader.h"
#endif
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

const int MAXN = 1e6 + 5;

vector<int> gr[MAXN];
int deg[MAXN], neig3[MAXN];
int p[MAXN], sz[MAXN];
int n, numcc, total, curcycle;
int great_node, big;
map<int, int> cnt;
set<int> three;
bool visit[MAXN];

void Init(int _n) {
	n = _n;
	for (int i = 0; i < n; i++) {
		neig3[i] = 0;
		deg[i] = 0;
		p[i] = -1;
		sz[i] = 1;
		gr[i].clear();
	}
	three.clear();
	numcc = n;
	total = n;
	big = 0;
	cnt.clear();
	cnt[0] = n;
}

int fin(int x) {
	return (p[x] == -1 ? x : p[x] = fin(p[x]));
}

inline void chval(int x, int add) {
	if (deg[x] == 3)
		three.erase(x);
	cnt[deg[x]]--;
	if (cnt[deg[x]] == 0)
		cnt.erase(deg[x]);
	deg[x] += add;
	cnt[deg[x]]++;
	if (deg[x] == 3)
		three.insert(x);
}

void dfs(int u) {
	visit[u] = true;
	for (auto v : gr[u]) {
		if (visit[v]) continue;
		dfs(v);
	}
}

bool check(int w) {
	for (auto v : gr[w])
		chval(v, -1);
	memset(visit, false, sizeof visit);
	visit[w] = true;
	chval(w, -((int)gr[w].size() + 1));
	assert(cnt[1] % 2 == 0);
	int comps = cnt[0] + cnt[1] / 2;
	int want = 0;
	/*
	int how_many = 0;
	for (auto it : cnt) {
		if (it.first > 3)
			how_many += it.second;
	}
	*/
	for (int u = 0; u < n; u++) {
		if (!visit[u]) {
			want++;
			dfs(u);
		}
	}
	chval(w, +((int)gr[w].size() + 1));
	for (auto v : gr[w])
		chval(v, +1);
	return want == comps;// && how_many == 0;
}

char str[100];

void Link(int a, int b) {
	//str[0] = '\0';
	if (deg[a] == 3) {
		for (auto v : gr[a])
			neig3[v]--;
		big++;
	}
	if (deg[b] == 3) {
		for (auto v : gr[b])
			neig3[v]--;
		big++;
	}
	chval(a, +1);
	chval(b, +1);
	gr[a].pb(b);
	gr[b].pb(a);
	if (deg[a] == 3) {
		for (auto v : gr[a])
			neig3[v]++;
	}
	if (deg[b] == 3) {
		for (auto v : gr[b])
			neig3[v]++;
	}
	if (deg[a] > 3) {
		great_node = a;
	} else if (deg[b] > 3) {
		great_node = b;
	}
	int ra = fin(a), rb = fin(b);
	if (ra != rb) {
		numcc--;
		if (sz[ra] > sz[rb]) {
			p[rb] = ra;
			sz[ra] += sz[rb];
		} else {
			p[ra] = rb;
			sz[rb] += sz[ra];
		}
	} else {
		curcycle = sz[ra];
	}
	if (ra == rb) {
		if (big == 1 && fin(great_node) != ra) {
			total = 0;
			return;
		} else if (big == 0 && cnt[3] > 0 && fin(*three.begin()) != ra) {
			total = 0;
			return;
		}
	}
	if (big == 0 && cnt[3] == 0) {
		// everything is either a chain or a cycle
		assert(cnt[1] % 2 == 0);
		int comps = cnt[0] + cnt[1] / 2;
		if (comps == numcc) {
			// every component is a chain
			total = n;
		} else if (comps == numcc - 1) {
			total = curcycle;
		} else {
			//sprintf(str, "IMPOSSIBLE");
			total = 0;
		}
	} else if (big > 1 || (false && cnt[3] > 4)) {
		/*if (big > 1) {
			if (cnt[3] > 4)
				sprintf(str, "big > 1 and cnt[3] > 4");
			else
				sprintf(str, "big > 1");
		} else {
			//sprintf(str, "cnt[3] > 4");
			//sprintf(str, "cnt[0] = %d, cnt[1] = %d, cnt[2] = %d, cnt[3] = %d, cnt[4] = %d", cnt[0], cnt[1], cnt[2], cnt[3], cnt[4]);
			if (three.size() <= 5) {
				for (auto it : three) {
					sprintf(str + strlen(str), "%d ", it);	
				}
			}
		}*/
		total = 0;
	} else if (big == 1) {
		if (neig3[great_node] != (int)three.size()) {
			//sprintf(str, "impossible great_node");
			total = 0;
		} else {
			bool found = (great_node == a || great_node == b);
			for (auto v : gr[a])
				if (v == great_node)
					found = true;
			for (auto v : gr[b])
				if (v == great_node)
					found = true;
			if (found || (ra == rb && total > 0)) {
				if (check(great_node)) {
					total = 1;
				} else {
					total = 0;
					//sprintf(str, "no great_node");
				}
			}
		}
	} else if (big == 0 && cnt[3] > 0) {
		// now big = 0 and cnt[3] > 0
		const int c = (int)three.size();
		set<int> proc;
		for (auto u : three) {
			proc.insert(u);
			for (auto v : gr[u])
				proc.insert(v);
		}
		bool found = false;
		for (auto it : proc) {
			if (it == a || it == b)
				found = true;
		}
		if (found || (ra == rb && total > 0)) {
			total = 0;
			for (auto u : proc) {
				if (deg[u] == 3 && neig3[u] == c - 1) {
					if (check(u))
						total++;
				} else if (deg[u] < 3 && neig3[u] == c) {
					if (check(u))
						total++;
				}
			}
			/*
			if (total == 0)
				sprintf(str, "no valid 3-degree nodes");
			else
				sprintf(str, "there are 3-degree nodes");
			*/
		}
		/* else {
			if (ra != rb || total == 0) return;
			total = 0;
			for (auto u : proc) {
				if (deg[u] == 3 && neig3[u] == c - 1) {
					if (check(u))
						total++;
				} else if (deg[u] < 3 && neig3[u] == c) {
					if (check(u))
						total++;
				}
			}
		}*/
	}
}

int CountCritical() {
	//puts(str);
	return total;
}


#endif

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