Submission #350373

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
350373	2021-01-19T05:19:54 Z	tengiz05	Parachute rings (IOI12_rings)	C++17	20 / 100	4000 ms	44752 KB

rings

#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int Ni = 1e6+5;
vector<int> edges[Ni];
int n, ans;
vector<int> p;
vector<int> sz;
int par(int u){
	if(p[u] == u)return u;
	return p[u] = par(p[u]);
}
bool IsSame(int u, int v){
	return par(u) == par(v);
}
void merge(int u,int v){
	u=par(u);v=par(v);
	if(u == v)return;
	p[v] = u;
	sz[u] += sz[v];
	return;
}
void Init(int N_) {
	n = N_;
	ans = n;
	p.assign(n,0);
	sz.assign(n,0);
	for(int i=0;i<n;i++)p[i] = i;
}
int number_of_cycles;

void Link(int u, int v){
	edges[u].pb(v);
	edges[v].pb(u);
	if(IsSame(u, v)){
		// idi na
		number_of_cycles++;
	}else {
		merge(u,v);
	}return;
}

int please_dont_go_there;
bool is_it_normal;
bool used[Ni];
void dfs(int u, int p){
	used[u] = true;
	int cnt= 0 ;
	for(auto v : edges[u]){
		if(v != please_dont_go_there)cnt++;
		if(v == p || v == please_dont_go_there)continue;
		if(used[v])is_it_normal = false;
		else dfs(v,u);
	}if(cnt>2)is_it_normal = false;
}
int CountCritical(){
	if(number_of_cycles > 1)return 0;
	ans = 0;
	for(int i=0;i<n;i++){
		// it's like: what if we delete this vertex?
		please_dont_go_there = i;
		for(int j=0;j<n;j++)used[j] = false;
		used[please_dont_go_there] = true;
		is_it_normal = true;
		for(int j=0;j<n;j++){
			if(!used[j])dfs(j,j);
		}
		if(is_it_normal)ans++;
	}return ans;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23788 KB	Output is correct
2	Correct	467 ms	24172 KB	Output is correct
3	Correct	684 ms	24124 KB	Output is correct
4	Correct	41 ms	23788 KB	Output is correct
5	Correct	240 ms	24044 KB	Output is correct
6	Correct	719 ms	24428 KB	Output is correct
7	Correct	236 ms	23944 KB	Output is correct
8	Correct	19 ms	24044 KB	Output is correct
9	Correct	724 ms	24188 KB	Output is correct
10	Correct	810 ms	24132 KB	Output is correct

Subtask #2

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	4024 ms	44752 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23788 KB	Output is correct
2	Correct	467 ms	24172 KB	Output is correct
3	Correct	684 ms	24124 KB	Output is correct
4	Correct	41 ms	23788 KB	Output is correct
5	Correct	240 ms	24044 KB	Output is correct
6	Correct	719 ms	24428 KB	Output is correct
7	Correct	236 ms	23944 KB	Output is correct
8	Correct	19 ms	24044 KB	Output is correct
9	Correct	724 ms	24188 KB	Output is correct
10	Correct	810 ms	24132 KB	Output is correct
11	Execution timed out	4091 ms	24128 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23788 KB	Output is correct
2	Correct	467 ms	24172 KB	Output is correct
3	Correct	684 ms	24124 KB	Output is correct
4	Correct	41 ms	23788 KB	Output is correct
5	Correct	240 ms	24044 KB	Output is correct
6	Correct	719 ms	24428 KB	Output is correct
7	Correct	236 ms	23944 KB	Output is correct
8	Correct	19 ms	24044 KB	Output is correct
9	Correct	724 ms	24188 KB	Output is correct
10	Correct	810 ms	24132 KB	Output is correct
11	Execution timed out	4091 ms	24128 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	23788 KB	Output is correct
2	Correct	467 ms	24172 KB	Output is correct
3	Correct	684 ms	24124 KB	Output is correct
4	Correct	41 ms	23788 KB	Output is correct
5	Correct	240 ms	24044 KB	Output is correct
6	Correct	719 ms	24428 KB	Output is correct
7	Correct	236 ms	23944 KB	Output is correct
8	Correct	19 ms	24044 KB	Output is correct
9	Correct	724 ms	24188 KB	Output is correct
10	Correct	810 ms	24132 KB	Output is correct
11	Execution timed out	4024 ms	44752 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-