답안 #601052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601052	2022-07-21T10:39:00 Z	Lucpp	Simurgh (IOI17_simurgh)	C++17	51 / 100	2600 ms	5248 KB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<pair<int, int>> edges;
vector<vector<pair<int, int>>> g;
vector<int> good;

void calc(int i){
	int start = edges[i].first, goal = edges[i].second;
	queue<int> q;
	q.push(start);
	vector<bool> vis(n);
	vis[start] = true;
	vector<pair<int, int>> last(n);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto [v, ind] : g[u]){
			if(ind == i || good[ind] == 0) continue;
			if(!vis[v]){
				vis[v] = true;
				q.push(v);
				last[v] = {u, ind};
			}
		}
	}
	if(!vis[goal]){ // bridge
		good[i] = true;
		return;
	}
	vector<int> cycle;
	vector<int> inCycle(m);
	int u = goal;
	while(u != start){
		inCycle[last[u].second] = true;
		cycle.push_back(last[u].second);
		u = last[u].first;
	}
	inCycle[i] = true;
	cycle.push_back(i);
	vector<int> forest;
	for(u = 0; u < n; u++){
		if(u != start){
			int e = last[u].second;
			if(!inCycle[e]) forest.push_back(e);
		}
	}
	int c = (int)cycle.size();
	vector<int> ans(c);
	for(int j = 0; j < c; j++){
		if(good[cycle[j]] == 1) ans[j] = -1;
		else{
			vector<int> v;
			for(int k = 0; k < c; k++){
				if(k != j) v.push_back(cycle[k]);
			}
			for(int e : forest) v.push_back(e);
			ans[j] = count_common_roads(v);
		}
	}
	for(int j = 0; j < c; j++){
		int ma = 0;
		for(int k = 0; k < c; k++){
			if(j != k) ma = max(ma, ans[k]);
		}
		good[cycle[j]] = ma > ans[j];
	}
}

vector<int> find_roads(int n_, vector<int> u, vector<int> v) {
	n = n_;
	m = (int)u.size();
	g.resize(n);
	for(int i = 0; i < m; i++){
		edges.emplace_back(u[i], v[i]);
		g[u[i]].emplace_back(v[i], i);
		g[v[i]].emplace_back(u[i], i);
	}
	good.resize(m, -1);
	for(int i = 0; i < m; i++){
		if(good[i] == -1){
			calc(i);
		}
	}
	vector<int> r;
	for(int i = 0; i < m; i++) if(good[i] == 1) r.push_back(i);
	return r;
}

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	220 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	1 ms	300 KB	correct
7	Correct	1 ms	296 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	0 ms	212 KB	correct
10	Correct	0 ms	212 KB	correct
11	Correct	1 ms	212 KB	correct
12	Correct	1 ms	212 KB	correct
13	Correct	1 ms	212 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	220 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	1 ms	300 KB	correct
7	Correct	1 ms	296 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	0 ms	212 KB	correct
10	Correct	0 ms	212 KB	correct
11	Correct	1 ms	212 KB	correct
12	Correct	1 ms	212 KB	correct
13	Correct	1 ms	212 KB	correct
14	Correct	7 ms	304 KB	correct
15	Correct	9 ms	384 KB	correct
16	Correct	8 ms	340 KB	correct
17	Correct	5 ms	372 KB	correct
18	Correct	2 ms	212 KB	correct
19	Correct	5 ms	340 KB	correct
20	Correct	5 ms	340 KB	correct
21	Correct	4 ms	340 KB	correct
22	Correct	5 ms	340 KB	correct
23	Correct	4 ms	340 KB	correct
24	Correct	3 ms	340 KB	correct
25	Correct	1 ms	212 KB	correct
26	Correct	3 ms	340 KB	correct
27	Correct	3 ms	340 KB	correct
28	Correct	1 ms	212 KB	correct
29	Correct	1 ms	212 KB	correct
30	Correct	3 ms	340 KB	correct
31	Correct	3 ms	344 KB	correct
32	Correct	3 ms	340 KB	correct
33	Correct	3 ms	340 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	220 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	1 ms	300 KB	correct
7	Correct	1 ms	296 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	0 ms	212 KB	correct
10	Correct	0 ms	212 KB	correct
11	Correct	1 ms	212 KB	correct
12	Correct	1 ms	212 KB	correct
13	Correct	1 ms	212 KB	correct
14	Correct	7 ms	304 KB	correct
15	Correct	9 ms	384 KB	correct
16	Correct	8 ms	340 KB	correct
17	Correct	5 ms	372 KB	correct
18	Correct	2 ms	212 KB	correct
19	Correct	5 ms	340 KB	correct
20	Correct	5 ms	340 KB	correct
21	Correct	4 ms	340 KB	correct
22	Correct	5 ms	340 KB	correct
23	Correct	4 ms	340 KB	correct
24	Correct	3 ms	340 KB	correct
25	Correct	1 ms	212 KB	correct
26	Correct	3 ms	340 KB	correct
27	Correct	3 ms	340 KB	correct
28	Correct	1 ms	212 KB	correct
29	Correct	1 ms	212 KB	correct
30	Correct	3 ms	340 KB	correct
31	Correct	3 ms	344 KB	correct
32	Correct	3 ms	340 KB	correct
33	Correct	3 ms	340 KB	correct
34	Correct	1984 ms	1996 KB	correct
35	Correct	1859 ms	1944 KB	correct
36	Correct	979 ms	1620 KB	correct
37	Correct	16 ms	340 KB	correct
38	Correct	2103 ms	1980 KB	correct
39	Correct	1587 ms	1812 KB	correct
40	Correct	993 ms	1616 KB	correct
41	Correct	2600 ms	1976 KB	correct
42	Correct	2516 ms	1976 KB	correct
43	Correct	779 ms	1376 KB	correct
44	Correct	513 ms	980 KB	correct
45	Correct	681 ms	1176 KB	correct
46	Correct	415 ms	992 KB	correct
47	Correct	114 ms	716 KB	correct
48	Correct	5 ms	300 KB	correct
49	Correct	18 ms	408 KB	correct
50	Correct	109 ms	620 KB	correct
51	Correct	724 ms	1180 KB	correct
52	Correct	525 ms	992 KB	correct
53	Correct	424 ms	980 KB	correct
54	Correct	771 ms	1368 KB	correct
55	Correct	673 ms	1204 KB	correct
56	Correct	619 ms	1188 KB	correct
57	Correct	629 ms	1192 KB	correct

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Incorrect	2007 ms	5248 KB	WA in grader: NO
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	220 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	1 ms	300 KB	correct
7	Correct	1 ms	296 KB	correct
8	Correct	1 ms	212 KB	correct
9	Correct	0 ms	212 KB	correct
10	Correct	0 ms	212 KB	correct
11	Correct	1 ms	212 KB	correct
12	Correct	1 ms	212 KB	correct
13	Correct	1 ms	212 KB	correct
14	Correct	7 ms	304 KB	correct
15	Correct	9 ms	384 KB	correct
16	Correct	8 ms	340 KB	correct
17	Correct	5 ms	372 KB	correct
18	Correct	2 ms	212 KB	correct
19	Correct	5 ms	340 KB	correct
20	Correct	5 ms	340 KB	correct
21	Correct	4 ms	340 KB	correct
22	Correct	5 ms	340 KB	correct
23	Correct	4 ms	340 KB	correct
24	Correct	3 ms	340 KB	correct
25	Correct	1 ms	212 KB	correct
26	Correct	3 ms	340 KB	correct
27	Correct	3 ms	340 KB	correct
28	Correct	1 ms	212 KB	correct
29	Correct	1 ms	212 KB	correct
30	Correct	3 ms	340 KB	correct
31	Correct	3 ms	344 KB	correct
32	Correct	3 ms	340 KB	correct
33	Correct	3 ms	340 KB	correct
34	Correct	1984 ms	1996 KB	correct
35	Correct	1859 ms	1944 KB	correct
36	Correct	979 ms	1620 KB	correct
37	Correct	16 ms	340 KB	correct
38	Correct	2103 ms	1980 KB	correct
39	Correct	1587 ms	1812 KB	correct
40	Correct	993 ms	1616 KB	correct
41	Correct	2600 ms	1976 KB	correct
42	Correct	2516 ms	1976 KB	correct
43	Correct	779 ms	1376 KB	correct
44	Correct	513 ms	980 KB	correct
45	Correct	681 ms	1176 KB	correct
46	Correct	415 ms	992 KB	correct
47	Correct	114 ms	716 KB	correct
48	Correct	5 ms	300 KB	correct
49	Correct	18 ms	408 KB	correct
50	Correct	109 ms	620 KB	correct
51	Correct	724 ms	1180 KB	correct
52	Correct	525 ms	992 KB	correct
53	Correct	424 ms	980 KB	correct
54	Correct	771 ms	1368 KB	correct
55	Correct	673 ms	1204 KB	correct
56	Correct	619 ms	1188 KB	correct
57	Correct	629 ms	1192 KB	correct
58	Correct	1 ms	212 KB	correct
59	Correct	1 ms	212 KB	correct
60	Incorrect	2007 ms	5248 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #601052

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 19.0

Subtask #5 0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 19.0

Subtask #5
0 / 30.0