Submission #1201827

#TimeUsernameProblemLanguageResultExecution timeMemory
1201827Zbyszek99Simurgh (IOI17_simurgh)C++20
0 / 100
3 ms6212 KiB
#include "simurgh.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; vector<pii> graph[501]; int val[501*501]; int edge_num[501][501]; vi end_points[501*501]; bool odw[501]; int pre[501]; int low[501]; int odw_path[501]; int cur_pre = 0; bool bridges[501*501]; vi known_tree; vi comp = {}; int n; void dfs_low(int v, int pop) { pre[v] = cur_pre++; low[v] = pre[v]; odw[v] = 1; forall(it,graph[v]) { if(it.ff != pop) { if(odw[it.ff]) { low[v] = min(pre[it.ff],low[v]); } else { dfs_low(it.ff,v); low[v] = min(low[v],low[it.ff]); if(low[it.ff] == pre[it.ff]) { bridges[it.ss] = 1; val[it.ss] = 1; known_tree.pb(it.ss); } } } } } void dfs_comp(int v) { comp.pb(v); odw[v] = 1; forall(it,graph[v]) { if(odw[it.ff] == 0 && !bridges[it.ss]) { dfs_comp(it.ff); } } } vi path; void gen_path(int v, int pop) { path.pb(v); if(odw[v] == 1 && v != pop) { return; } forall(it,graph[v]) { if(!bridges[it.ss] && it.ff != pop && (odw[it.ff] == 0 || v != pop)) { gen_path(it.ff,v); return; } } } vi cur_p; vi doc_path; int ci = 0; void dfs_path(int v, int doc) { cur_p.pb(v); if(v == doc) { doc_path = cur_p; return; } odw_path[v] = ci; forall(it,graph[v]) { if(odw[it.ff] == 1 && odw_path[it.ff] != ci) { dfs_path(it.ff,doc); if(siz(doc_path) != 0) return; } } cur_p.pop_back(); } vi rng_tree; void find_random_tree(int v) { odw_path[v] = ci; forall(it,graph[v]) { if(odw_path[it.ff] != ci) { rng_tree.pb(it.ss); find_random_tree(it.ff); } } } void find_cycle_vals(vi edge, vi verts) { rng_tree = {}; ci++; forall(it,verts) odw_path[it] = ci; forall(it,verts) find_random_tree(it); forall(it,edge) known_tree.pb(it); int ke = -1; forall(it,edge) if(val[it] != -1) ke = it; if(ke != -1) { vi query_tree = rng_tree; forall(it,edge) if(it != ke) query_tree.pb(it); int ke_val = count_common_roads(query_tree); rep(i,siz(edge)-1) query_tree.pop_back(); forall(it,edge) { if(val[it] != -1) continue; forall(it2,edge) { if(it != it2) query_tree.pb(it2); } if(ke_val == count_common_roads(query_tree)) val[it] = val[ke]; else val[it] = val[ke] ^ 1; rep(i,siz(edge)-1) query_tree.pop_back(); } } else { vi query_tree = rng_tree; int max_ = -1e9; int min_ = 1e9; forall(it,edge) { if(val[it] != -1) continue; forall(it2,edge) { if(it != it2) query_tree.pb(it2); } val[it] = count_common_roads(query_tree); min_ = min(min_,val[it]); max_ = max(max_,val[it]); rep(i,siz(edge)-1) query_tree.pop_back(); } if(min_ == max_) forall(it,edge) val[it] = 0; else { forall(it,edge) { if(val[it] == min_) val[it] = 1; else val[it] = 0; } } } } int rep_[501]; int fint(int v) { if(rep_[v] == v) return v; rep_[v] = fint(rep_[v]); return rep_[v]; } void onion(int a, int b) { rep_[fint(a)] = fint(b); } int count_forest_val(vi f) { rep(i,n) rep_[i] = i; int known_sum = 0; vi query_tree = f; forall(it,f) onion(end_points[it][0],end_points[it][1]); forall(it,known_tree) { if(fint(end_points[it][0]) != fint(end_points[it][1])) { known_sum += val[it]; query_tree.pb(it); onion(end_points[it][0],end_points[it][1]); } } return count_common_roads(query_tree) - known_sum; } vi find_roads(int N, vi u, vi v) { n = N; rep(i,siz(u)) { val[i] = -1; end_points[i] = {v[i],u[i]}; graph[u[i]].pb({v[i],i}); graph[v[i]].pb({u[i],i}); edge_num[u[i]][v[i]] = i; edge_num[v[i]][u[i]] = i; } dfs_low(0,0); rep(i,n) odw[i] = 0; rep(i,n) { if(odw[i] == 0) { comp = {}; dfs_comp(i); if(siz(comp) == 1) continue; forall(it,comp) { odw[it] = 0; } queue<int> q; q.push(i); odw[i] = 1; while(!q.empty()) { int t = q.front(); q.pop(); while(true) { path = {}; gen_path(t,t); if(siz(path) == 1) break; ci++; cur_p = {}; doc_path = {}; dfs_path(path.back(),path[0]); forall(it,path) { if(odw[it] == 0) { q.push(it); } odw[it] = 1; } vi total_path = path; total_path.pop_back(); forall(it,doc_path) total_path.pb(it); vi cycle_edges; rep(i,siz(total_path)-1) { cycle_edges.pb(edge_num[total_path[i]][total_path[i+1]]); } find_cycle_vals(cycle_edges,total_path); } } } } rep(i,n) { vi unknown; forall(it,graph[i]) { if(val[it.ss] == -1) unknown.pb(it.ss); } int deg = count_forest_val(unknown); if(deg == 0) { forall(it,graph[i]) { if(val[it.ss] == -1) val[it.ss] = 0; } continue; } rep(j,deg) { vi s; forall(it,unknown) if(val[it] == -1) s.pb(it); while(siz(s) != 1) { vi left; vi right; rep(i,siz(s)/2) left.pb(s[i]); rep(i,(siz(s)+1)/2) right.pb(s[i]); if(count_forest_val(left) > 0) s = left; else s = right; } val[s[0]] = 1; } } vi ans; rep(i,siz(u)) { if(val[i] == 1) ans.pb(i); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...