Submission #1109913

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109913	2024-11-08T04:00:16 Z	santi3223	Parachute rings (IOI12_rings)	C++14	20 / 100	4000 ms	29268 KB

rings

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vl vector<ll>
#define vs vector<string>
#define vb vector<bool>
#define ull unsigned long long
#define pll pair<ll, ll>
#define pb push_back
#define fi first
#define se second
#define ff(i, p, x) for (ll i = p; i < x; i++)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define ed "\n"
#define IO std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll MOD = 1e9+7;

ll n, q;
vb visited;
vector<vl> conexiones;
bool ok;

void Init(int N_){
	n = N_;
	conexiones = vector<vl>(n);
}

void Link(int a, int b){
	conexiones[a].pb(b);
	conexiones[b].pb(a);
}

void dfs(ll cur, ll ban){
	if(visited[cur]){
		return;
	}
	visited[cur] = true;
	ll c = 0;
	
	for(auto &x : conexiones[cur]){
		if(x != ban){
			c++;
		}
	}
	if(c > 2){
		ok = false;
		return;
	}
	if(c == 0){
		q = 2;
	}
	else if(c == 1){
		q++;
	}
	
	for(auto &x : conexiones[cur]){
		if(x != ban){
			dfs(x, ban);
		}
	}
}

int CountCritical(){
	ll c = 0;
	ff(i, 0, n){
		visited = vb(n, false);
		ok = true;
		ff(j, 0, n){
			if(!visited[j] && i != j){
				q = 0;
				dfs(j, i);
				if(q != 2){
					ok = false;
					break;
				}
			}
		}
		
		if(ok){
			c++;
		}
	}
	
	return c;
}

//fuerza bruta pa el sub 1, sale?

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	57 ms	592 KB	Output is correct
3	Correct	11 ms	592 KB	Output is correct
4	Correct	5 ms	508 KB	Output is correct
5	Correct	104 ms	680 KB	Output is correct
6	Correct	369 ms	848 KB	Output is correct
7	Correct	4 ms	760 KB	Output is correct
8	Correct	39 ms	592 KB	Output is correct
9	Correct	53 ms	592 KB	Output is correct
10	Correct	33 ms	592 KB	Output is correct

Subtask #2

0 / 17.0

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

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	57 ms	592 KB	Output is correct
3	Correct	11 ms	592 KB	Output is correct
4	Correct	5 ms	508 KB	Output is correct
5	Correct	104 ms	680 KB	Output is correct
6	Correct	369 ms	848 KB	Output is correct
7	Correct	4 ms	760 KB	Output is correct
8	Correct	39 ms	592 KB	Output is correct
9	Correct	53 ms	592 KB	Output is correct
10	Correct	33 ms	592 KB	Output is correct
11	Execution timed out	4056 ms	648 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	57 ms	592 KB	Output is correct
3	Correct	11 ms	592 KB	Output is correct
4	Correct	5 ms	508 KB	Output is correct
5	Correct	104 ms	680 KB	Output is correct
6	Correct	369 ms	848 KB	Output is correct
7	Correct	4 ms	760 KB	Output is correct
8	Correct	39 ms	592 KB	Output is correct
9	Correct	53 ms	592 KB	Output is correct
10	Correct	33 ms	592 KB	Output is correct
11	Execution timed out	4056 ms	648 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	57 ms	592 KB	Output is correct
3	Correct	11 ms	592 KB	Output is correct
4	Correct	5 ms	508 KB	Output is correct
5	Correct	104 ms	680 KB	Output is correct
6	Correct	369 ms	848 KB	Output is correct
7	Correct	4 ms	760 KB	Output is correct
8	Correct	39 ms	592 KB	Output is correct
9	Correct	53 ms	592 KB	Output is correct
10	Correct	33 ms	592 KB	Output is correct
11	Execution timed out	4078 ms	29268 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-