oj.uz

Submission #446553

# Submission time Handle Problem Language Result Execution time Memory
446553 2021-07-22T12:09:00 Z ComPhyPark Parachute rings (IOI12_rings) C++14
100 / 100
 3816 ms 123740 KB 
#include<cstdio>
#include<vector>
using namespace std;
const int SZ = 1000010;
int min(int a, int b) { return a < b ? a : b; }
int n;
const bool ifDebug = false;
int cycleNum;
vector<int>l[SZ];
typedef struct Graph {
	int st[4], ts[3];
	int p[SZ], sz[SZ], ln[SZ];
	bool is3E[SZ], isCX[SZ];
	int x;
	void init() {
		x = n;
		st[0] = ts[0] = n;
		st[1] = st[2] = st[3] = ts[1] = ts[2] = 0;
		for (int i = 0; i < n; i++) {
			p[i] = i;
			sz[i] = 1;
			ln[i] = 0;
			is3E[i] = isCX[i] = false;
		}
	}
	void init(int X) {
		if (ifDebug)printf("init(%d)\n", X);
		init();
		x = X;
		PR();
		for (int i = 0; i < n; i++) {
			for (int e : l[i]) {
				if (e < i) {
					if (e == x || i == x) {
						isCX[e + i - x] = true;
						continue;
					}
					int a = f(e), b = f(i);
					if (a != b) {
						p[b] = a;
						ln[a] += ln[b];
						sz[a] += sz[b];
					}
					ln[a]++;
				}
			}
		}
		st[0] = st[1] = st[2] = st[3] = ts[1] = ts[2] = 0;
		for (int i = 0; i < n; i++) {
			st[min(gC(i), 3)]++;
			is3E[i] = false;
		}
		for (int i = 0; i < n; i++) {
			if (gC(i) > 2)is3E[f(i)] = true;
		}
		for (int i = 0; i < n; i++) {
			if (i == p[i])ts[gT(i)]++;
		}
	}
	int f(int a) {
		return a == p[a] ? a : p[a] = f(p[a]);
	}
	int gC(int A) {
		if (A == x)return 0;
		return l[A].size() - (isCX[A] ? 1 : 0);
	}
	void u(int A, int B) {
		int a = f(A), b = f(B);
		if (a != b) {
			p[b] = a;
			ts[gT(a)]--;
			ts[gT(b)]--;
			ln[a] += ln[b];
			sz[a] += sz[b];
			is3E[a] |= is3E[b];
		}
		else {
			ts[gT(a)]--;
		}
	}
	void Con(int A, int B) {
		int a = f(A);
		if (x == n) {
			st[min(gC(A), 3)]--;
			l[A].push_back(B);
			st[min(gC(A), 3)]++;
		}
		else {
			st[min(gC(A) - 1, 3)]--;
			st[min(gC(A), 3)]++;
		}
		if (gC(A) >= 3)is3E[a] = true;
	}
	int gT(int a) {
		if (is3E[a]) {
			return 2;
		}
		else if (sz[a] == ln[a]) {
			return 1;
		}
		else {
			return 0;
		}
	}
	void Link(int A, int B) {
		if (A == x || B == x) {
			isCX[A + B - x] = true;
			return;
		}
		if (ifDebug)printf("%d:%d-%d\n", x, A, B);
		u(A, B);
		Con(A, B);
		Con(B, A);
		int a = f(A);
		ln[a]++;
		ts[gT(a)]++;
	}
	bool isChain() {
		return (ts[1] + ts[2] == 0);
	}
	void PR() {
		if (!ifDebug)return;
		printf("-------%d-------\n", x);
		printf("%d %d %d %d\n", st[0], st[1], st[2], st[3]);
		printf("%d %d %d\n", ts[0], ts[1], ts[2]);
		for (int a = 0; a < n; a++) {
			printf("(%d)", gC(a));
			if (a == p[a]) {
				printf("[%d(%d,%d,%d)]", a, sz[a], gT(a), ln[a]);
				printf("\n");
			}
			else {
				printf("%d->%d\n", a, f(a));
			}
		}
		printf("-----------------\n");
	}
}Graph;
Graph MG, GV[4];
int GS;
void Init(int N) {
	cycleNum = n = N;
	MG.init();
}
void Link(int A, int B) {
	bool p = (MG.st[3] == 0);
	MG.Link(A, B);
	for (int i = 0; i < GS; i++) {
		GV[i].Link(A, B);
	}
	if (MG.gT(MG.f(A)) == 1)cycleNum = MG.f(A);
	if (MG.gT(MG.f(B)) == 1)cycleNum = MG.f(B);
	if (p && MG.st[3]) {
		if (ifDebug)printf("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
		int a = A;
		if (l[A].size() < 3)a = B;
		GS = l[a].size() + 1;
		GV[l[a].size()].init(a);
		for (int i = 0; i < l[a].size(); i++) {
			GV[i].init(l[a][i]);
		}
	}
}
int CountCritical() {
	if (MG.ts[2]) {
		if (ifDebug)printf(">=3 Exists");
		int r = 0;
		for (int i = 0; i < GS; i++) {
			if (GV[i].isChain())r++;
		}
		return r;
	}
	else if (MG.ts[1]) {
		if (ifDebug)printf("cycle Exists");
		if (MG.ts[1] > 1)return 0;
		return MG.sz[cycleNum];
	}
	else {
		if (ifDebug)printf("Already Chain");
		return n;
	}
}

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:159:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |   for (int i = 0; i < l[a].size(); i++) {
      |                   ~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23756 KB Output is correct
2 Correct 19 ms 24360 KB Output is correct
3 Correct 20 ms 24476 KB Output is correct
4 Correct 16 ms 23892 KB Output is correct
5 Correct 17 ms 23880 KB Output is correct
6 Correct 17 ms 23984 KB Output is correct
7 Correct 18 ms 24268 KB Output is correct
8 Correct 17 ms 24032 KB Output is correct
9 Correct 20 ms 24480 KB Output is correct
10 Correct 23 ms 24396 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 47332 KB Output is correct
2 Correct 2447 ms 103676 KB Output is correct
3 Correct 3816 ms 119432 KB Output is correct
4 Correct 1142 ms 68816 KB Output is correct
5 Correct 1148 ms 68708 KB Output is correct
6 Correct 1115 ms 67784 KB Output is correct
7 Correct 3608 ms 119132 KB Output is correct
8 Correct 2450 ms 117384 KB Output is correct
9 Correct 2333 ms 123740 KB Output is correct
10 Correct 833 ms 67544 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23756 KB Output is correct
2 Correct 19 ms 24360 KB Output is correct
3 Correct 20 ms 24476 KB Output is correct
4 Correct 16 ms 23892 KB Output is correct
5 Correct 17 ms 23880 KB Output is correct
6 Correct 17 ms 23984 KB Output is correct
7 Correct 18 ms 24268 KB Output is correct
8 Correct 17 ms 24032 KB Output is correct
9 Correct 20 ms 24480 KB Output is correct
10 Correct 23 ms 24396 KB Output is correct
11 Correct 20 ms 24396 KB Output is correct
12 Correct 26 ms 24908 KB Output is correct
13 Correct 23 ms 24960 KB Output is correct
14 Correct 22 ms 24812 KB Output is correct
15 Correct 22 ms 25456 KB Output is correct
16 Correct 20 ms 24268 KB Output is correct
17 Correct 25 ms 24920 KB Output is correct
18 Correct 25 ms 25652 KB Output is correct
19 Correct 20 ms 24324 KB Output is correct
20 Correct 23 ms 24976 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23756 KB Output is correct
2 Correct 19 ms 24360 KB Output is correct
3 Correct 20 ms 24476 KB Output is correct
4 Correct 16 ms 23892 KB Output is correct
5 Correct 17 ms 23880 KB Output is correct
6 Correct 17 ms 23984 KB Output is correct
7 Correct 18 ms 24268 KB Output is correct
8 Correct 17 ms 24032 KB Output is correct
9 Correct 20 ms 24480 KB Output is correct
10 Correct 23 ms 24396 KB Output is correct
11 Correct 20 ms 24396 KB Output is correct
12 Correct 26 ms 24908 KB Output is correct
13 Correct 23 ms 24960 KB Output is correct
14 Correct 22 ms 24812 KB Output is correct
15 Correct 22 ms 25456 KB Output is correct
16 Correct 20 ms 24268 KB Output is correct
17 Correct 25 ms 24920 KB Output is correct
18 Correct 25 ms 25652 KB Output is correct
19 Correct 20 ms 24324 KB Output is correct
20 Correct 23 ms 24976 KB Output is correct
21 Correct 34 ms 25576 KB Output is correct
22 Correct 45 ms 26524 KB Output is correct
23 Correct 61 ms 27204 KB Output is correct
24 Correct 134 ms 31888 KB Output is correct
25 Correct 45 ms 31040 KB Output is correct
26 Correct 122 ms 32528 KB Output is correct
27 Correct 66 ms 27692 KB Output is correct
28 Correct 166 ms 32744 KB Output is correct
29 Correct 93 ms 32452 KB Output is correct
30 Correct 76 ms 28220 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23756 KB Output is correct
2 Correct 19 ms 24360 KB Output is correct
3 Correct 20 ms 24476 KB Output is correct
4 Correct 16 ms 23892 KB Output is correct
5 Correct 17 ms 23880 KB Output is correct
6 Correct 17 ms 23984 KB Output is correct
7 Correct 18 ms 24268 KB Output is correct
8 Correct 17 ms 24032 KB Output is correct
9 Correct 20 ms 24480 KB Output is correct
10 Correct 23 ms 24396 KB Output is correct
11 Correct 483 ms 47332 KB Output is correct
12 Correct 2447 ms 103676 KB Output is correct
13 Correct 3816 ms 119432 KB Output is correct
14 Correct 1142 ms 68816 KB Output is correct
15 Correct 1148 ms 68708 KB Output is correct
16 Correct 1115 ms 67784 KB Output is correct
17 Correct 3608 ms 119132 KB Output is correct
18 Correct 2450 ms 117384 KB Output is correct
19 Correct 2333 ms 123740 KB Output is correct
20 Correct 833 ms 67544 KB Output is correct
21 Correct 20 ms 24396 KB Output is correct
22 Correct 26 ms 24908 KB Output is correct
23 Correct 23 ms 24960 KB Output is correct
24 Correct 22 ms 24812 KB Output is correct
25 Correct 22 ms 25456 KB Output is correct
26 Correct 20 ms 24268 KB Output is correct
27 Correct 25 ms 24920 KB Output is correct
28 Correct 25 ms 25652 KB Output is correct
29 Correct 20 ms 24324 KB Output is correct
30 Correct 23 ms 24976 KB Output is correct
31 Correct 34 ms 25576 KB Output is correct
32 Correct 45 ms 26524 KB Output is correct
33 Correct 61 ms 27204 KB Output is correct
34 Correct 134 ms 31888 KB Output is correct
35 Correct 45 ms 31040 KB Output is correct
36 Correct 122 ms 32528 KB Output is correct
37 Correct 66 ms 27692 KB Output is correct
38 Correct 166 ms 32744 KB Output is correct
39 Correct 93 ms 32452 KB Output is correct
40 Correct 76 ms 28220 KB Output is correct
41 Correct 248 ms 39232 KB Output is correct
42 Correct 1053 ms 97316 KB Output is correct
43 Correct 488 ms 90816 KB Output is correct
44 Correct 2410 ms 115172 KB Output is correct
45 Correct 2511 ms 113072 KB Output is correct
46 Correct 778 ms 61752 KB Output is correct
47 Correct 974 ms 62272 KB Output is correct
48 Correct 1266 ms 109132 KB Output is correct
49 Correct 746 ms 63260 KB Output is correct
50 Correct 796 ms 62732 KB Output is correct
51 Correct 646 ms 83296 KB Output is correct
52 Correct 1982 ms 97092 KB Output is correct
53 Correct 1334 ms 109460 KB Output is correct
54 Correct 2385 ms 104740 KB Output is correct
55 Correct 3068 ms 112028 KB Output is correct