답안 #949688

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
949688 2024-03-19T15:13:48 Z qin Simurgh (IOI17_simurgh) C++17
30 / 100
89 ms 24696 KB
#include <bits/stdc++.h>
#include "simurgh.h"
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1;
struct graph{
		vv<vv<pii>> g;
		vv<int> vis;
		vv<vv<int>> queries;
		vv<int> res, taken;
		vv<int> av;
		void init(int n, int m){
				g.resize(n), vis.resize(n); // trzeba pamietać, że są indeksowane od 0 do n-1 !!!
				queries.resize(m), res.resize(m, -1), taken.resize(m, 0), av.resize(m);
		}
		void add_edge(int a, int b, int i){ g[a].emplace_back(b, i), g[b].emplace_back(a, i); }
		void dfs(int x, int c, vv<int> &edges){
				vis[x] = c;
				for(pii &u : g[x]) if(!vis[u.fi]) edges.emplace_back(u.se), dfs(u.fi, c, edges);
		}
		vv<int> prep_colour(int x, int &c){
				int l = 0; fill(all(vis), 0);
				vis[x] = inf;
				vv<int> edges;
				for(pii &u : g[x]) if(!vis[u.fi]) dfs(u.fi, ++l, edges);
				c = l;
				return edges;
		}
		void dfs_check(int x){
				vis[x] = 1;
				for(pii &u : g[x]) if(!vis[u.fi] && av[u.se]) dfs_check(u.fi);
		}
		bool check_tree(vv<int> tmp){
				fill(all(av), 0), fill(all(vis), 0);
				bool ret = 1;
				if(ssize(tmp) != ssize(g)-1) ret = 0;
				for(int u : tmp) av[u] = 1;
				dfs_check(0);
				for(int u : vis) if(!u) ret = 0;
				return ret;
		}
		vv<int> get_roads(){
				int n = ssize(g);
				for(int i = 0; i < n; ++i){
						int k = 0;
						vv<int> edges = prep_colour(i, k);
						vv<vv<int>> t(k+1);
						for(pii &u : g[i]) t[vis[u.fi]].emplace_back(u.se);
						for(int j = 1; j <= k; ++j){
								int mx = -1;
								vv<int> equal_to_max;
								for(int u : t[j]){
												vv<int> tmp = edges;
												for(int l = 1; l <= k; ++l) if(l != j) tmp.emplace_back(t[l].back());
												tmp.emplace_back(u);
												//~ assert(ssize(tmp) == ssize(g)-1);
												//~ printf("a %d %d %d\n", i, j, u);
												//~ for(int u : tmp) printf("%d ", u);
												//~ pn;
												//~ assert(check_tree(tmp));
												int ask = count_common_roads(tmp);
												if(ask > mx) equal_to_max.clear();
												if(ask >= mx) mx = ask, equal_to_max.emplace_back(u);
												tmp.pop_back(), queries[u] = tmp, res[u] = ask;
										
								}
								for(int u : equal_to_max) taken[u] = 1;
						}
				}
				vv<int> result;
				for(int i = 0; i < ssize(taken); ++i) if(taken[i]) result.emplace_back(i);//, printf("%d\n", i);
				assert(ssize(result) == ssize(g)-1);
				return result;
		}
};
vv<int> find_roads(int n, vv<int> u, vv<int> v){
		graph g; g.init(n, ssize(u));
		for(int i = 0; i < ssize(u); ++i) g.add_edge(u[i], v[i], i);
		return g.get_roads();
}
#ifdef LOCAL
int main(){
		int T = 1;
		for(++T; --T; ) answer();
		return 0;
}
#endif
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 0 ms 436 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 1 ms 344 KB correct
8 Correct 1 ms 344 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 1 ms 348 KB correct
11 Correct 1 ms 348 KB correct
12 Correct 1 ms 348 KB correct
13 Correct 1 ms 348 KB correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 0 ms 436 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 1 ms 344 KB correct
8 Correct 1 ms 344 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 1 ms 348 KB correct
11 Correct 1 ms 348 KB correct
12 Correct 1 ms 348 KB correct
13 Correct 1 ms 348 KB correct
14 Correct 2 ms 856 KB correct
15 Correct 2 ms 604 KB correct
16 Correct 2 ms 604 KB correct
17 Correct 2 ms 604 KB correct
18 Correct 1 ms 348 KB correct
19 Correct 2 ms 604 KB correct
20 Correct 2 ms 604 KB correct
21 Correct 2 ms 604 KB correct
22 Correct 1 ms 604 KB correct
23 Correct 1 ms 604 KB correct
24 Correct 1 ms 604 KB correct
25 Correct 1 ms 344 KB correct
26 Correct 1 ms 604 KB correct
27 Correct 1 ms 604 KB correct
28 Correct 1 ms 348 KB correct
29 Correct 1 ms 348 KB correct
30 Correct 2 ms 604 KB correct
31 Correct 1 ms 604 KB correct
32 Correct 1 ms 604 KB correct
33 Correct 1 ms 604 KB correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 0 ms 436 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 1 ms 344 KB correct
8 Correct 1 ms 344 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 1 ms 348 KB correct
11 Correct 1 ms 348 KB correct
12 Correct 1 ms 348 KB correct
13 Correct 1 ms 348 KB correct
14 Correct 2 ms 856 KB correct
15 Correct 2 ms 604 KB correct
16 Correct 2 ms 604 KB correct
17 Correct 2 ms 604 KB correct
18 Correct 1 ms 348 KB correct
19 Correct 2 ms 604 KB correct
20 Correct 2 ms 604 KB correct
21 Correct 2 ms 604 KB correct
22 Correct 1 ms 604 KB correct
23 Correct 1 ms 604 KB correct
24 Correct 1 ms 604 KB correct
25 Correct 1 ms 344 KB correct
26 Correct 1 ms 604 KB correct
27 Correct 1 ms 604 KB correct
28 Correct 1 ms 348 KB correct
29 Correct 1 ms 348 KB correct
30 Correct 2 ms 604 KB correct
31 Correct 1 ms 604 KB correct
32 Correct 1 ms 604 KB correct
33 Correct 1 ms 604 KB correct
34 Incorrect 89 ms 23416 KB WA in grader: NO
35 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Incorrect 71 ms 24696 KB WA in grader: NO
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 0 ms 436 KB correct
5 Correct 0 ms 348 KB correct
6 Correct 0 ms 348 KB correct
7 Correct 1 ms 344 KB correct
8 Correct 1 ms 344 KB correct
9 Correct 0 ms 348 KB correct
10 Correct 1 ms 348 KB correct
11 Correct 1 ms 348 KB correct
12 Correct 1 ms 348 KB correct
13 Correct 1 ms 348 KB correct
14 Correct 2 ms 856 KB correct
15 Correct 2 ms 604 KB correct
16 Correct 2 ms 604 KB correct
17 Correct 2 ms 604 KB correct
18 Correct 1 ms 348 KB correct
19 Correct 2 ms 604 KB correct
20 Correct 2 ms 604 KB correct
21 Correct 2 ms 604 KB correct
22 Correct 1 ms 604 KB correct
23 Correct 1 ms 604 KB correct
24 Correct 1 ms 604 KB correct
25 Correct 1 ms 344 KB correct
26 Correct 1 ms 604 KB correct
27 Correct 1 ms 604 KB correct
28 Correct 1 ms 348 KB correct
29 Correct 1 ms 348 KB correct
30 Correct 2 ms 604 KB correct
31 Correct 1 ms 604 KB correct
32 Correct 1 ms 604 KB correct
33 Correct 1 ms 604 KB correct
34 Incorrect 89 ms 23416 KB WA in grader: NO
35 Halted 0 ms 0 KB -