Submission #595927

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
595927	2022-07-14T08:08:29 Z	fuad27	Parachute rings (IOI12_rings)	C++17	20 / 100	4000 ms	200420 KB

rings

#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int n;
vector<int> g[N];
vector<vector<int>> v(N, vector<int> (N,0));
void Init(int N_) {
	n = N_;
}

void Link(int A, int B) {
	if(v[A][B])return;
	g[A].push_back(B);
	g[B].push_back(A);
	v[A][B]=1;
	v[B][A]=1;
}
int cur;
bool check;
bool vis[N];
void dfs(int at, int p) {
	if(vis[at])return;
	vis[at]=1;
	int cnt=0;
	for(int to:g[at]) {
		if(to == p or to == cur)continue;
		if(vis[to]){
			check=false;
			return;
		}
		dfs(to,at);
		cnt++;
	}
	if(cnt>1)check=false;
}
int CountCritical() {
	// cout<<"$$$$"<<endl;
	int ans=0;
	for(int j = 0;j<n;j++) {
		cur=j;
		check=1;
		for(int i = 0;i<n;i++)vis[i]=0;
		for(int i = 0;i<n;i++) {
			if(i == j)continue;
			int deg=0;
			for(int j:g[i]) {
				if(j!=cur)deg++;
			}
			if(deg<=1 and !vis[i]){
				dfs(i,-1);
			}
		}
		for(int i = 0;i<n;i++) {
			if(i==cur)continue;
			if(!vis[i]){
				check=false;
				// cout<<i<<" ";
			}
		}
		ans+=check;
	}
	return ans;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	98780 KB	Output is correct
2	Correct	479 ms	98876 KB	Output is correct
3	Correct	665 ms	98892 KB	Output is correct
4	Correct	71 ms	98848 KB	Output is correct
5	Correct	203 ms	99036 KB	Output is correct
6	Correct	666 ms	99264 KB	Output is correct
7	Correct	258 ms	98848 KB	Output is correct
8	Correct	153 ms	98972 KB	Output is correct
9	Correct	629 ms	99128 KB	Output is correct
10	Correct	808 ms	99148 KB	Output is correct

Subtask #2

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	138 ms	200420 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	98780 KB	Output is correct
2	Correct	479 ms	98876 KB	Output is correct
3	Correct	665 ms	98892 KB	Output is correct
4	Correct	71 ms	98848 KB	Output is correct
5	Correct	203 ms	99036 KB	Output is correct
6	Correct	666 ms	99264 KB	Output is correct
7	Correct	258 ms	98848 KB	Output is correct
8	Correct	153 ms	98972 KB	Output is correct
9	Correct	629 ms	99128 KB	Output is correct
10	Correct	808 ms	99148 KB	Output is correct
11	Execution timed out	4046 ms	98944 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	98780 KB	Output is correct
2	Correct	479 ms	98876 KB	Output is correct
3	Correct	665 ms	98892 KB	Output is correct
4	Correct	71 ms	98848 KB	Output is correct
5	Correct	203 ms	99036 KB	Output is correct
6	Correct	666 ms	99264 KB	Output is correct
7	Correct	258 ms	98848 KB	Output is correct
8	Correct	153 ms	98972 KB	Output is correct
9	Correct	629 ms	99128 KB	Output is correct
10	Correct	808 ms	99148 KB	Output is correct
11	Execution timed out	4046 ms	98944 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	98780 KB	Output is correct
2	Correct	479 ms	98876 KB	Output is correct
3	Correct	665 ms	98892 KB	Output is correct
4	Correct	71 ms	98848 KB	Output is correct
5	Correct	203 ms	99036 KB	Output is correct
6	Correct	666 ms	99264 KB	Output is correct
7	Correct	258 ms	98848 KB	Output is correct
8	Correct	153 ms	98972 KB	Output is correct
9	Correct	629 ms	99128 KB	Output is correct
10	Correct	808 ms	99148 KB	Output is correct
11	Runtime error	138 ms	200420 KB	Execution killed with signal 11
12	Halted	0 ms	0 KB	-