Submission #949726

#	Time	Username	Problem	Language	Result	Execution time	Memory
949726		qin	Simurgh (IOI17_simurgh)	C++17	30 / 100	88 ms	24212 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