Submission #949688

#	Time	Username	Problem	Language	Result	Execution time	Memory
949688		qin	Simurgh (IOI17_simurgh)	C++17	30 / 100	89 ms	24696 KiB

simurgh

#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

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30