Submission #851278

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
851278	2023-09-19T09:29:23 Z	Halym2007	Parachute rings (IOI12_rings)	C++17	55 / 100	4000 ms	101696 KB

rings

//#include "rings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define pb push_back
const int MAXM = 1e6 + 5;
#define ff first
#define ss second
vector <int> v[MAXM];
int n, comp, cycle, san[MAXM], tr;
bool rem[MAXM], vis[MAXM], gir, birgezek;
int bol[MAXM], oo;
bool bolonok = 0;
vector <int> ayyr, ko;
void Init(int N) {
	n = N;
}

void dfs (int x, int pr) {
	vis[x] = 1;
	for (int i : v[x]) {
		if (rem[i] or i == pr) continue;
		if (vis[i]) {
			cycle = 1;
			continue;
		}
		dfs (i, x);
	} 
}

void dfs1 (int x, int pr) {
	san[x] = 1;
	comp++;
	for (int i : v[x]) {
		if (i == pr or rem[i]) continue;
		if (san[i]) {
			cycle = 1;
			continue;
		}
		dfs1 (i, x);
	}
}

int CountCritical() {
	if ((int)ko.sz > 1) return 0;
	if (bolonok) return 0;
	int jogap = 0;
	if (!birgezek) {
		for (int i = 0; i < n; ++i) {
			if ((int)v[i].sz > 3) {
				ayyr.clear();
				ayyr.pb (i);
				break;
			}
		}
		if (ayyr.empty()) {
			for (int i = 0; i < n; ++i) {
				if ((int)v[i].sz == 3) {
					ayyr.pb (i);
					for (int j : v[i]) {
						ayyr.pb (j);
					}
					break;
				}
			}
		}
	}
	if (!ayyr.empty()) {
		birgezek = 1;
		for (int i : ayyr) {
			rem[i] = 1;
			cycle = 0;
			for (int j = 0; j < n; ++j) {
				san[j] = (int)v[j].sz;
			}
			for (int j = 0; j < n; ++j) {
				if (rem[j] or vis[j]) continue;
				dfs (j, -1);
			}
			for (int j : v[i]) {
				san[j]--;
			}
			san[i] = 0;
			bool aa = 0;
			if (cycle) aa = 1;
			for (int j = 0; j < n; ++j) {
				if (san[j] > 2) aa = 1;
				san[j] = vis[j] = 0;
			}
			rem[i] = 0;
			if (!aa) {
				jogap++;
			}
		}
		if (!jogap) bolonok = 1;
		return jogap;			
	}
	else {
		int opysy = 0;
		int jogap1 = 0;
		for (int i = 0; i < n; ++i) {
			if (!san[i]) {
				cycle = 0;
				comp = 0;
				dfs1 (i, -1);
				opysy += cycle;
				if (cycle) {
					jogap = comp;
				}	
				else {
					jogap1 += comp;
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			san[i] = 0;
		}
		if (opysy > 1) {
			bolonok = 1;
			return 0;
		}
		else if (opysy == 1) return jogap;
		else return jogap1;
	}
	return n;
}

void Link(int a, int b) {
	v[a].pb (b);
	v[b].pb (a);
	if ((int)ko.sz > 1) return;
	if ((int)v[a].sz > 3) {
		if (ko.empty()) ko.pb (a);
		else if (ko[0] != a) ko.pb (a);
	}
	if ((int)ko.sz > 1) return;
	if ((int)v[b].sz > 3) {
		if (ko.empty()) ko.pb (b);
		else if (ko[0] != b) ko.pb (b);
	}
}

 
//#include <stdio.h>
//#include <stdlib.h>
//#include <assert.h>
//
//#define inbuf_len 1 << 16
//#define outbuf_len 1 << 16
//
//int main() {
//	freopen("input3.txt", "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;
//
//}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	25176 KB	Output is correct
2	Correct	7 ms	27736 KB	Output is correct
3	Correct	7 ms	27480 KB	Output is correct
4	Correct	6 ms	25180 KB	Output is correct
5	Correct	6 ms	25432 KB	Output is correct
6	Correct	7 ms	25688 KB	Output is correct
7	Correct	6 ms	27224 KB	Output is correct
8	Correct	6 ms	25436 KB	Output is correct
9	Correct	8 ms	27724 KB	Output is correct
10	Correct	8 ms	27480 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	275 ms	50588 KB	Output is correct
2	Correct	651 ms	65716 KB	Output is correct
3	Correct	515 ms	65360 KB	Output is correct
4	Correct	804 ms	73040 KB	Output is correct
5	Correct	761 ms	73756 KB	Output is correct
6	Correct	818 ms	101696 KB	Output is correct
7	Correct	493 ms	64080 KB	Output is correct
8	Correct	1402 ms	72052 KB	Output is correct
9	Correct	1575 ms	75412 KB	Output is correct
10	Correct	584 ms	75264 KB	Output is correct

Subtask #3

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	25176 KB	Output is correct
2	Correct	7 ms	27736 KB	Output is correct
3	Correct	7 ms	27480 KB	Output is correct
4	Correct	6 ms	25180 KB	Output is correct
5	Correct	6 ms	25432 KB	Output is correct
6	Correct	7 ms	25688 KB	Output is correct
7	Correct	6 ms	27224 KB	Output is correct
8	Correct	6 ms	25436 KB	Output is correct
9	Correct	8 ms	27724 KB	Output is correct
10	Correct	8 ms	27480 KB	Output is correct
11	Correct	15 ms	25432 KB	Output is correct
12	Correct	25 ms	25948 KB	Output is correct
13	Correct	36 ms	25688 KB	Output is correct
14	Correct	16 ms	25432 KB	Output is correct
15	Correct	23 ms	27480 KB	Output is correct
16	Correct	20 ms	25952 KB	Output is correct
17	Correct	9 ms	25944 KB	Output is correct
18	Correct	9 ms	25944 KB	Output is correct
19	Correct	22 ms	25692 KB	Output is correct
20	Correct	46 ms	25828 KB	Output is correct

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	25176 KB	Output is correct
2	Correct	7 ms	27736 KB	Output is correct
3	Correct	7 ms	27480 KB	Output is correct
4	Correct	6 ms	25180 KB	Output is correct
5	Correct	6 ms	25432 KB	Output is correct
6	Correct	7 ms	25688 KB	Output is correct
7	Correct	6 ms	27224 KB	Output is correct
8	Correct	6 ms	25436 KB	Output is correct
9	Correct	8 ms	27724 KB	Output is correct
10	Correct	8 ms	27480 KB	Output is correct
11	Correct	15 ms	25432 KB	Output is correct
12	Correct	25 ms	25948 KB	Output is correct
13	Correct	36 ms	25688 KB	Output is correct
14	Correct	16 ms	25432 KB	Output is correct
15	Correct	23 ms	27480 KB	Output is correct
16	Correct	20 ms	25952 KB	Output is correct
17	Correct	9 ms	25944 KB	Output is correct
18	Correct	9 ms	25944 KB	Output is correct
19	Correct	22 ms	25692 KB	Output is correct
20	Correct	46 ms	25828 KB	Output is correct
21	Execution timed out	4019 ms	26584 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	25176 KB	Output is correct
2	Correct	7 ms	27736 KB	Output is correct
3	Correct	7 ms	27480 KB	Output is correct
4	Correct	6 ms	25180 KB	Output is correct
5	Correct	6 ms	25432 KB	Output is correct
6	Correct	7 ms	25688 KB	Output is correct
7	Correct	6 ms	27224 KB	Output is correct
8	Correct	6 ms	25436 KB	Output is correct
9	Correct	8 ms	27724 KB	Output is correct
10	Correct	8 ms	27480 KB	Output is correct
11	Correct	275 ms	50588 KB	Output is correct
12	Correct	651 ms	65716 KB	Output is correct
13	Correct	515 ms	65360 KB	Output is correct
14	Correct	804 ms	73040 KB	Output is correct
15	Correct	761 ms	73756 KB	Output is correct
16	Correct	818 ms	101696 KB	Output is correct
17	Correct	493 ms	64080 KB	Output is correct
18	Correct	1402 ms	72052 KB	Output is correct
19	Correct	1575 ms	75412 KB	Output is correct
20	Correct	584 ms	75264 KB	Output is correct
21	Correct	15 ms	25432 KB	Output is correct
22	Correct	25 ms	25948 KB	Output is correct
23	Correct	36 ms	25688 KB	Output is correct
24	Correct	16 ms	25432 KB	Output is correct
25	Correct	23 ms	27480 KB	Output is correct
26	Correct	20 ms	25952 KB	Output is correct
27	Correct	9 ms	25944 KB	Output is correct
28	Correct	9 ms	25944 KB	Output is correct
29	Correct	22 ms	25692 KB	Output is correct
30	Correct	46 ms	25828 KB	Output is correct
31	Execution timed out	4019 ms	26584 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-