답안 #119229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
119229	2019-06-20T17:02:55 Z	ioilolcom	낙하산 고리들 (IOI12_rings)	C++14	20 / 100	4000 ms	104196 KB

rings

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pii pair<int,int>
#define x first
#define y second
typedef long long int ll;
int N;
const int M=1e6+7;
set<int> adj[M];
int parent[M];
struct DSU {
	DSU(int n){
		for(int i=0; i<N; i++) parent[i] = i;
	}
	inline int find(int a){
		if(parent[a] != a) parent[a] = find(parent[a]);
		return parent[a];
	}
	inline void merge(int a,int b){
		int pa = find(a);
		int pb = find(b);
		parent[pa] = pb;
	}
};
void Init(int N_) {
	N = N_;
}
vector<pii> edges;
void Link(int A, int B) {
	adj[A].insert(B);
	adj[B].insert(A);
	edges.push_back({A,B});
}
bool is(int l){
	DSU dsu(N);
	int deg[N+1];
	for(int i=0; i<N; i++) {
		deg[i]=0;
	}
	for(auto m:edges) {
		if(m.x==l||m.y==l) {
			continue;
		}
		if(dsu.find(m.x)==dsu.find(m.y)) {
			return 0;
		}
		dsu.merge(m.x,m.y);
		deg[m.x]++;
		deg[m.y]++;
	}
	for(int i=0; i<N; i++) {
		if(deg[i]>2) {
			return 0;
		}
	}
	return 1;
}
int CountCritical() {
	int ans=0;
	for(int x=0; x<N; x++) ans+=is(x);
	return ans;
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	47352 KB	Output is correct
2	Correct	184 ms	47824 KB	Output is correct
3	Correct	275 ms	47912 KB	Output is correct
4	Correct	46 ms	47348 KB	Output is correct
5	Correct	110 ms	47864 KB	Output is correct
6	Correct	343 ms	48064 KB	Output is correct
7	Correct	74 ms	47352 KB	Output is correct
8	Correct	178 ms	47816 KB	Output is correct
9	Correct	303 ms	47988 KB	Output is correct
10	Correct	257 ms	47992 KB	Output is correct

Subtask #2

0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	4053 ms	104196 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	47352 KB	Output is correct
2	Correct	184 ms	47824 KB	Output is correct
3	Correct	275 ms	47912 KB	Output is correct
4	Correct	46 ms	47348 KB	Output is correct
5	Correct	110 ms	47864 KB	Output is correct
6	Correct	343 ms	48064 KB	Output is correct
7	Correct	74 ms	47352 KB	Output is correct
8	Correct	178 ms	47816 KB	Output is correct
9	Correct	303 ms	47988 KB	Output is correct
10	Correct	257 ms	47992 KB	Output is correct
11	Execution timed out	4086 ms	48044 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	47352 KB	Output is correct
2	Correct	184 ms	47824 KB	Output is correct
3	Correct	275 ms	47912 KB	Output is correct
4	Correct	46 ms	47348 KB	Output is correct
5	Correct	110 ms	47864 KB	Output is correct
6	Correct	343 ms	48064 KB	Output is correct
7	Correct	74 ms	47352 KB	Output is correct
8	Correct	178 ms	47816 KB	Output is correct
9	Correct	303 ms	47988 KB	Output is correct
10	Correct	257 ms	47992 KB	Output is correct
11	Execution timed out	4086 ms	48044 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	42 ms	47352 KB	Output is correct
2	Correct	184 ms	47824 KB	Output is correct
3	Correct	275 ms	47912 KB	Output is correct
4	Correct	46 ms	47348 KB	Output is correct
5	Correct	110 ms	47864 KB	Output is correct
6	Correct	343 ms	48064 KB	Output is correct
7	Correct	74 ms	47352 KB	Output is correct
8	Correct	178 ms	47816 KB	Output is correct
9	Correct	303 ms	47988 KB	Output is correct
10	Correct	257 ms	47992 KB	Output is correct
11	Execution timed out	4053 ms	104196 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-