Submission #1079206

#TimeUsernameProblemLanguageResultExecution timeMemory
1079206GraySimurgh (IOI17_simurgh)C++17
0 / 100
1 ms348 KiB
#include "simurgh.h" #include <bits/stdc++.h> using namespace std; #define ll int #define ff first #define ss second #define ln "\n" #define ld long double vector<pair<ll, ll>> e; vector<vector<ll>> A; // Slow version vector<ll> checka; void dfs(ll u, vector<bool> &vis, ll mask){ vis[u]=1; for (auto i:A[u]){ if (mask&(1<<i)){ ll v = e[i].ff^e[i].ss^u; if (vis[v]) continue; dfs(v, vis, mask); } } } bool check(ll mask, ll n, ll m){ checka.clear(); vector<bool> vis(n); dfs(0, vis, mask); for (ll i=0; i<n; i++) if (!vis[i]) return 0; for (ll i=0; i<m; i++){ if (mask&(1<<i)) checka.push_back(i); } return 1; } vector<int> find_roads_slow(int _n, vector<int> u, vector<int> v) { int n=_n, m=u.size(); e.resize(m); A.clear(); A.resize(n); for (ll i=0; i<m; i++){ e[i]={u[i], v[i]}; A[u[i]].push_back(i); A[v[i]].push_back(i); } vector<ll> ans; for (ll i=0; i<(1ll<<m); i++){ if (__builtin_popcount(i)==n-1){ if (check(i, n, m)) { ll ret = count_common_roads(checka); if (ret==n-1){ ans=checka; break; } } } } return ans; } ll n, m; vector<bool> isBridge; ll findBridge(ll u, ll p, vector<ll> &tin, vector<ll> &tmin, ll &timer){ tin[u]=tmin[u]=timer++; ll cnt=0; for (auto i:A[u]){ ll v = e[i].ff^e[i].ss^u; if (v==p) continue; if (tin[v]==-1) cnt+=findBridge(v, u, tin, tmin, timer); tmin[u]=min(tmin[u], tmin[v]); if (tin[u]<tmin[v]){ cnt++; isBridge[i]=1; } } return cnt; } vector<bool> noroyal; void findST(ll u, vector<bool> &vis, vector<ll> &edges){ vis[u]=1; for (auto i:A[u]){ if (noroyal[i]) continue; ll v = e[i].ff^e[i].ss^u; if (vis[v]) continue; edges.push_back(i); findST(v, vis, edges); } } struct DSU{ vector<ll> p; ll sz; DSU(ll N){ sz=N; p.resize(N+1, -1); } ll get(ll x){ return (p[x]==-1?x:p[x]=get(p[x])); } bool unite(ll u, ll v){ u=get(u); v=get(v); if (u==v) return 0; p[u]=v; return 1; } }; ll seek(vector<ll> incl, ll excl, ll inicnt){ DSU tr(n); vector<ll> checkarr; for (auto i:incl){ if (i==excl) continue; checkarr.push_back(i); tr.unite(e[i].ff, e[i].ss); } for (ll i=0; i<m; i++){ if (i==excl) continue; if (tr.get(e[i].ff)!=tr.get(e[i].ss)){ checkarr.push_back(i); ll ret=count_common_roads(checkarr); if (ret>inicnt) return i; checkarr.pop_back(); } } return excl; } vector<int> find_roads(int _n, vector<int> u, vector<int> v) { n=_n; m=u.size(); e.clear(); e.resize(m); A.clear(); A.resize(n); for (ll i=0; i<m; i++){ e[i]={u[i], v[i]}; A[u[i]].push_back(i); A[v[i]].push_back(i); } isBridge.clear(); isBridge.resize(m); vector<ll> tin(n, -1), tmin(n, -1); ll timer=0; ll bcnt=findBridge(0, 0, tin, tmin, timer); vector<ll> ans; // assert(bcnt); // cout << bcnt << ln; if (bcnt==n-1){ for (ll i=0; i<m; i++) ans.push_back(i); return ans; } noroyal.clear(); noroyal.resize(m, 0); vector<bool> vis(n); vector<ll> edges; ll ret; while (true){ edges.clear(); vis.assign(n, 0); findST(0, vis, edges); ret = count_common_roads(edges); if (ret>bcnt) break; else{ ll count=0; for (auto i:edges){ if (!isBridge[i]) {noroyal[i]=1;count++;} } assert(count); } } // ret = count_common_roads(edges); assert(ret); for (auto i:edges){ if (isBridge[i]) { ans.push_back(i); }else{ ans.push_back(seek(edges, i, ret)); } } // cout << "CAME" << ln; 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...