oj.uz

Submission #561779

# Submission time Handle Problem Language Result Execution time Memory
561779 2022-05-13T13:22:17 Z drkarlicio2107 Parachute rings (IOI12_rings) C++14
100 / 100
 723 ms 80256 KB 
#include <bits/stdc++.h>
using namespace std;
int N; int ima=0, tre=0;
pair <int, int> g [1000010];
struct rijesi {
	int par [1000010];
	int dub [1000010];
	int deg [1000010];
	int c=-1, md=0, zab=-1;
	void dod (int a, int b){
		if (a==zab || b==zab || md>2) return ;
		//cout << a << " " << b << " " << zab << endl;
		deg [a]++; deg [b]++;
		md=max (md, max (deg [a], deg [b]));
		while (par [a]!=-1) a=par [a];
		while (par [b]!=-1) b=par [b];
		if (dub [b]>dub [a]) swap (a, b);
		//cout << dub [a] << " " << dub [b] << endl;
		if (a==b){
			if (c>-1) c=0;
			else c=dub [a];
		}
		else {
			dub [a]+=dub [b];
			par [b]=a;
		}
		return ;
	}
	int ans (){
		if (ima && c!=-1) return 0;
		if (md>2) return 0;
		if (c==-1) return N;
		return c; 
	}
} sol [10];
void Link (int a, int b){
	a++; b++;
	sol [0].dod (a, b);
	g [tre]={a, b};
	tre++;
	if (!ima){
		if (sol [0].md>2){
			for (int i=1; i<N+1; i++){
				if (sol [0].deg [i]>2) sol [ima=1].zab=i;
			}
			for (int i=0; i<tre; i++){
				if (g [i].first==sol [1].zab) sol [++ima].zab=g[i].second;
				if (g [i].second==sol [1].zab) sol [++ima].zab=g[i].first;
			}
			for (int i=1; i<5; i++){
				for (int j=0; j<tre; j++){
					sol [i].dod (g [j].first, g [j].second);
				}
			}
		}
	}
	else {
		for (int i=1; i<=4; i++) sol [i].dod (a, b);
	}
	return ;
}
int CountCritical (){
	//cout << ima << endl;
	int x=0;
	if (ima){
		for (int i=1; i<5; i++) x+=(sol [i].ans()>0);
	}
	else x=sol [0].ans();
	return x;
}
void Init (int n){
	for (int i=0; i<5; i++){
		for (int j=1; j<n+10; j++) sol[i].dub [j]=1;
		memset (sol[i].par, -1, sizeof (sol[i].par));
		memset (sol[i].deg, 0, sizeof (sol[i].deg));
	}
	N=n;
	/*for (int i=0; i<n; i++){
		string type; cin >> type;
		if (type=="CountCritical"){
			cout << CountCritical() << endl;
		}
		else {
			int a,b; cin >> a >> b;
			Link (a, b);
		}
	}*/
	return ;
}
/*int main (){
	cin >> n;
	Init (n);
	return 0;
}*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39508 KB Output is correct
2 Correct 17 ms 39604 KB Output is correct
3 Correct 18 ms 39664 KB Output is correct
4 Correct 20 ms 39500 KB Output is correct
5 Correct 15 ms 39636 KB Output is correct
6 Correct 17 ms 39636 KB Output is correct
7 Correct 17 ms 39596 KB Output is correct
8 Correct 16 ms 39700 KB Output is correct
9 Correct 18 ms 39712 KB Output is correct
10 Correct 16 ms 39636 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 53700 KB Output is correct
2 Correct 382 ms 72052 KB Output is correct
3 Correct 234 ms 74956 KB Output is correct
4 Correct 405 ms 80188 KB Output is correct
5 Correct 443 ms 80256 KB Output is correct
6 Correct 446 ms 79616 KB Output is correct
7 Correct 216 ms 78220 KB Output is correct
8 Correct 616 ms 77724 KB Output is correct
9 Correct 723 ms 80220 KB Output is correct
10 Correct 326 ms 79040 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39508 KB Output is correct
2 Correct 17 ms 39604 KB Output is correct
3 Correct 18 ms 39664 KB Output is correct
4 Correct 20 ms 39500 KB Output is correct
5 Correct 15 ms 39636 KB Output is correct
6 Correct 17 ms 39636 KB Output is correct
7 Correct 17 ms 39596 KB Output is correct
8 Correct 16 ms 39700 KB Output is correct
9 Correct 18 ms 39712 KB Output is correct
10 Correct 16 ms 39636 KB Output is correct
11 Correct 18 ms 39732 KB Output is correct
12 Correct 24 ms 39836 KB Output is correct
13 Correct 19 ms 39920 KB Output is correct
14 Correct 22 ms 39892 KB Output is correct
15 Correct 17 ms 40044 KB Output is correct
16 Correct 19 ms 39940 KB Output is correct
17 Correct 18 ms 39948 KB Output is correct
18 Correct 18 ms 40052 KB Output is correct
19 Correct 17 ms 39892 KB Output is correct
20 Correct 18 ms 39848 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39508 KB Output is correct
2 Correct 17 ms 39604 KB Output is correct
3 Correct 18 ms 39664 KB Output is correct
4 Correct 20 ms 39500 KB Output is correct
5 Correct 15 ms 39636 KB Output is correct
6 Correct 17 ms 39636 KB Output is correct
7 Correct 17 ms 39596 KB Output is correct
8 Correct 16 ms 39700 KB Output is correct
9 Correct 18 ms 39712 KB Output is correct
10 Correct 16 ms 39636 KB Output is correct
11 Correct 18 ms 39732 KB Output is correct
12 Correct 24 ms 39836 KB Output is correct
13 Correct 19 ms 39920 KB Output is correct
14 Correct 22 ms 39892 KB Output is correct
15 Correct 17 ms 40044 KB Output is correct
16 Correct 19 ms 39940 KB Output is correct
17 Correct 18 ms 39948 KB Output is correct
18 Correct 18 ms 40052 KB Output is correct
19 Correct 17 ms 39892 KB Output is correct
20 Correct 18 ms 39848 KB Output is correct
21 Correct 27 ms 41232 KB Output is correct
22 Correct 35 ms 42252 KB Output is correct
23 Correct 40 ms 43016 KB Output is correct
24 Correct 45 ms 42640 KB Output is correct
25 Correct 29 ms 41940 KB Output is correct
26 Correct 42 ms 42896 KB Output is correct
27 Correct 45 ms 42984 KB Output is correct
28 Correct 36 ms 42964 KB Output is correct
29 Correct 35 ms 42540 KB Output is correct
30 Correct 41 ms 43340 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39508 KB Output is correct
2 Correct 17 ms 39604 KB Output is correct
3 Correct 18 ms 39664 KB Output is correct
4 Correct 20 ms 39500 KB Output is correct
5 Correct 15 ms 39636 KB Output is correct
6 Correct 17 ms 39636 KB Output is correct
7 Correct 17 ms 39596 KB Output is correct
8 Correct 16 ms 39700 KB Output is correct
9 Correct 18 ms 39712 KB Output is correct
10 Correct 16 ms 39636 KB Output is correct
11 Correct 180 ms 53700 KB Output is correct
12 Correct 382 ms 72052 KB Output is correct
13 Correct 234 ms 74956 KB Output is correct
14 Correct 405 ms 80188 KB Output is correct
15 Correct 443 ms 80256 KB Output is correct
16 Correct 446 ms 79616 KB Output is correct
17 Correct 216 ms 78220 KB Output is correct
18 Correct 616 ms 77724 KB Output is correct
19 Correct 723 ms 80220 KB Output is correct
20 Correct 326 ms 79040 KB Output is correct
21 Correct 18 ms 39732 KB Output is correct
22 Correct 24 ms 39836 KB Output is correct
23 Correct 19 ms 39920 KB Output is correct
24 Correct 22 ms 39892 KB Output is correct
25 Correct 17 ms 40044 KB Output is correct
26 Correct 19 ms 39940 KB Output is correct
27 Correct 18 ms 39948 KB Output is correct
28 Correct 18 ms 40052 KB Output is correct
29 Correct 17 ms 39892 KB Output is correct
30 Correct 18 ms 39848 KB Output is correct
31 Correct 27 ms 41232 KB Output is correct
32 Correct 35 ms 42252 KB Output is correct
33 Correct 40 ms 43016 KB Output is correct
34 Correct 45 ms 42640 KB Output is correct
35 Correct 29 ms 41940 KB Output is correct
36 Correct 42 ms 42896 KB Output is correct
37 Correct 45 ms 42984 KB Output is correct
38 Correct 36 ms 42964 KB Output is correct
39 Correct 35 ms 42540 KB Output is correct
40 Correct 41 ms 43340 KB Output is correct
41 Correct 147 ms 56564 KB Output is correct
42 Correct 429 ms 68408 KB Output is correct
43 Correct 216 ms 63224 KB Output is correct
44 Correct 219 ms 76748 KB Output is correct
45 Correct 299 ms 73216 KB Output is correct
46 Correct 329 ms 74592 KB Output is correct
47 Correct 388 ms 75100 KB Output is correct
48 Correct 226 ms 69484 KB Output is correct
49 Correct 341 ms 77360 KB Output is correct
50 Correct 368 ms 76812 KB Output is correct
51 Correct 195 ms 61048 KB Output is correct
52 Correct 223 ms 70292 KB Output is correct
53 Correct 203 ms 69264 KB Output is correct
54 Correct 553 ms 73684 KB Output is correct
55 Correct 402 ms 75996 KB Output is correct