답안 #834746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834746	2023-08-22T18:10:54 Z	Josia	Simurgh (IOI17_simurgh)	C++17	51 / 100	278 ms	3956 KB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;





int query(set<int> x) {
	vector<int> edges;
	for (int i: x) edges.push_back(i);
	return count_common_roads(edges);
}



int n, m;

vector<vector<int>> graphList;
vector<vector<int>> graphMatrix;
vector<vector<int>> knownEdges;


struct solve {
	vector<int> vis;
	set<int> usedEdges;

	void dfs(int v, int p, int forbidden, int col) {
		if (vis[v]!=-1) return;
		vis[v] = col;

		if (p!=-1) {
			usedEdges.insert(graphMatrix[v][p]);
		}

		for (int u: graphList[v]) {
			if (u == forbidden) continue;
			dfs(u, v, forbidden, col);
		}
	}


	void start(int v) {
		vis.assign(n, -1);
		usedEdges.clear();
		int col = 0;
		vector<vector<int>> colors;
		for (int u: graphList[v]) {
			if (vis[u]==-1) {
				dfs(u, -1, v, col);
				col++;
				colors.push_back({});
			}

			colors[vis[u]].push_back(u);
		}

		for (auto i: colors) usedEdges.insert(graphMatrix[v][i[0]]);

		for (auto i: colors) {
			vector<int> vals;
			usedEdges.erase(graphMatrix[v][i[0]]);
			int hi = -1;
			for (int j: i) {
				if (knownEdges[v][j] != -1 && hi == -1) {
					usedEdges.insert(graphMatrix[v][j]);
					vals.push_back(query(usedEdges));
					usedEdges.erase(graphMatrix[v][j]);
					if (knownEdges[v][j] == 1) hi = vals.back();
					if (knownEdges[v][j] == 0) hi = vals.back()+1;
					continue;
				}
				if (knownEdges[v][j] != -1 && hi != -1) {
					if (knownEdges[v][j] == 1) vals.push_back(hi);
					if (knownEdges[v][j] == 0) vals.push_back(hi-1);
					continue;
				}
				usedEdges.insert(graphMatrix[v][j]);
				vals.push_back(query(usedEdges));
				usedEdges.erase(graphMatrix[v][j]);
			}
			usedEdges.insert(graphMatrix[v][i[0]]);
			if (hi == -1) hi = *max_element(vals.begin(), vals.end());

			for (int j = 0; j<(int)i.size(); j++) {
				if (vals[j] == hi) {
					knownEdges[i[j]][v] = 1;
					knownEdges[v][i[j]] = 1;
				}
				else {
					knownEdges[i[j]][v] = 0;
					knownEdges[v][i[j]] = 0;
				}
			}
		}
	}


	vector<int> output;
	solve() {
		for (int i = 0; i<n; i++) {
			start(i);
		}
		output.clear();

		for (int i = 0; i<n; i++) {
			for (int j = i+1; j<n; j++) {
				if (knownEdges[i][j]==0) continue;
				if (knownEdges[i][j]==-1) continue;
				// assert(knownEdges[i][j]==1);

				output.push_back(graphMatrix[i][j]);
			}
		}
	}
};



vector<int> find_roads(int _n, vector<int> u, vector<int> v) {
	n = _n;
	m = u.size();
	graphList.assign(n, vector<int>());
	graphMatrix.assign(n, vector<int>(n, -1));
	knownEdges.assign(n, vector<int>(n, -1));

	for (int i = 0; i<m; i++) {
		graphList[u[i]].push_back(v[i]);
		graphList[v[i]].push_back(u[i]);

		graphMatrix[u[i]][v[i]] = i;
		graphMatrix[v[i]][u[i]] = i;
	}

	solve sol;

	return sol.output;
}

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	0 ms	212 KB	correct
7	Correct	0 ms	212 KB	correct
8	Correct	0 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	0 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	0 ms	212 KB	correct
7	Correct	0 ms	212 KB	correct
8	Correct	0 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	4 ms	340 KB	correct
15	Correct	6 ms	340 KB	correct
16	Correct	6 ms	364 KB	correct
17	Correct	3 ms	340 KB	correct
18	Correct	2 ms	340 KB	correct
19	Correct	3 ms	340 KB	correct
20	Correct	3 ms	340 KB	correct
21	Correct	3 ms	340 KB	correct
22	Correct	3 ms	340 KB	correct
23	Correct	2 ms	340 KB	correct
24	Correct	2 ms	300 KB	correct
25	Correct	2 ms	296 KB	correct
26	Correct	2 ms	340 KB	correct
27	Correct	4 ms	340 KB	correct
28	Correct	2 ms	340 KB	correct
29	Correct	1 ms	340 KB	correct
30	Correct	4 ms	340 KB	correct
31	Correct	2 ms	340 KB	correct
32	Correct	4 ms	340 KB	correct
33	Correct	2 ms	340 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	0 ms	212 KB	correct
7	Correct	0 ms	212 KB	correct
8	Correct	0 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	4 ms	340 KB	correct
15	Correct	6 ms	340 KB	correct
16	Correct	6 ms	364 KB	correct
17	Correct	3 ms	340 KB	correct
18	Correct	2 ms	340 KB	correct
19	Correct	3 ms	340 KB	correct
20	Correct	3 ms	340 KB	correct
21	Correct	3 ms	340 KB	correct
22	Correct	3 ms	340 KB	correct
23	Correct	2 ms	340 KB	correct
24	Correct	2 ms	300 KB	correct
25	Correct	2 ms	296 KB	correct
26	Correct	2 ms	340 KB	correct
27	Correct	4 ms	340 KB	correct
28	Correct	2 ms	340 KB	correct
29	Correct	1 ms	340 KB	correct
30	Correct	4 ms	340 KB	correct
31	Correct	2 ms	340 KB	correct
32	Correct	4 ms	340 KB	correct
33	Correct	2 ms	340 KB	correct
34	Correct	269 ms	1652 KB	correct
35	Correct	270 ms	1760 KB	correct
36	Correct	189 ms	1492 KB	correct
37	Correct	22 ms	852 KB	correct
38	Correct	278 ms	1652 KB	correct
39	Correct	234 ms	1584 KB	correct
40	Correct	184 ms	1492 KB	correct
41	Correct	267 ms	1652 KB	correct
42	Correct	267 ms	1748 KB	correct
43	Correct	148 ms	1368 KB	correct
44	Correct	124 ms	1108 KB	correct
45	Correct	152 ms	1272 KB	correct
46	Correct	125 ms	1108 KB	correct
47	Correct	55 ms	980 KB	correct
48	Correct	15 ms	724 KB	correct
49	Correct	23 ms	852 KB	correct
50	Correct	54 ms	980 KB	correct
51	Correct	147 ms	1152 KB	correct
52	Correct	121 ms	1196 KB	correct
53	Correct	110 ms	1164 KB	correct
54	Correct	148 ms	1340 KB	correct
55	Correct	140 ms	1256 KB	correct
56	Correct	140 ms	1260 KB	correct
57	Correct	140 ms	1260 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	180 ms	3956 KB	WA in grader: NO
4	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	correct
2	Correct	1 ms	212 KB	correct
3	Correct	1 ms	212 KB	correct
4	Correct	0 ms	212 KB	correct
5	Correct	1 ms	212 KB	correct
6	Correct	0 ms	212 KB	correct
7	Correct	0 ms	212 KB	correct
8	Correct	0 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	4 ms	340 KB	correct
15	Correct	6 ms	340 KB	correct
16	Correct	6 ms	364 KB	correct
17	Correct	3 ms	340 KB	correct
18	Correct	2 ms	340 KB	correct
19	Correct	3 ms	340 KB	correct
20	Correct	3 ms	340 KB	correct
21	Correct	3 ms	340 KB	correct
22	Correct	3 ms	340 KB	correct
23	Correct	2 ms	340 KB	correct
24	Correct	2 ms	300 KB	correct
25	Correct	2 ms	296 KB	correct
26	Correct	2 ms	340 KB	correct
27	Correct	4 ms	340 KB	correct
28	Correct	2 ms	340 KB	correct
29	Correct	1 ms	340 KB	correct
30	Correct	4 ms	340 KB	correct
31	Correct	2 ms	340 KB	correct
32	Correct	4 ms	340 KB	correct
33	Correct	2 ms	340 KB	correct
34	Correct	269 ms	1652 KB	correct
35	Correct	270 ms	1760 KB	correct
36	Correct	189 ms	1492 KB	correct
37	Correct	22 ms	852 KB	correct
38	Correct	278 ms	1652 KB	correct
39	Correct	234 ms	1584 KB	correct
40	Correct	184 ms	1492 KB	correct
41	Correct	267 ms	1652 KB	correct
42	Correct	267 ms	1748 KB	correct
43	Correct	148 ms	1368 KB	correct
44	Correct	124 ms	1108 KB	correct
45	Correct	152 ms	1272 KB	correct
46	Correct	125 ms	1108 KB	correct
47	Correct	55 ms	980 KB	correct
48	Correct	15 ms	724 KB	correct
49	Correct	23 ms	852 KB	correct
50	Correct	54 ms	980 KB	correct
51	Correct	147 ms	1152 KB	correct
52	Correct	121 ms	1196 KB	correct
53	Correct	110 ms	1164 KB	correct
54	Correct	148 ms	1340 KB	correct
55	Correct	140 ms	1256 KB	correct
56	Correct	140 ms	1260 KB	correct
57	Correct	140 ms	1260 KB	correct
58	Correct	1 ms	212 KB	correct
59	Correct	1 ms	212 KB	correct
60	Incorrect	180 ms	3956 KB	WA in grader: NO
61	Halted	0 ms	0 KB	-

답안 #834746

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