Submission #1079290

#TimeUsernameProblemLanguageResultExecution timeMemory
1079290GraySimurgh (IOI17_simurgh)C++17
0 / 100
0 ms440 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 struct DSU{ vector<ll> p; ll sz; DSU(ll N){ sz=N; p.resize(sz, -1); } ll get(ll x){ return p[x]==-1?x:p[x]=get(p[x]); } void unite(ll a, ll b){ a=get(a); b=get(b); if (a==b) return; p[a]=b; } }; ll n, m; vector<vector<ll>> A; vector<pair<ll, ll>> e; ll heavyedge(vector<ll> &edges, ll excl, ll ret){ DSU tr(n); vector<ll> check; for (auto edge:edges){ if (excl==edge) continue; check.push_back(edge); tr.unite(e[edge].ff, e[edge].ss); } for (ll i=0; i<m; i++){ if (i==excl) continue; if (tr.get(e[i].ff)==tr.get(e[i].ss)) continue; check.push_back(i); if (count_common_roads(check)>ret){ return i; } check.pop_back(); } return excl; } vector<int> find_roads(int _n, vector<int> u, vector<int> v) { assert(A.empty()); n=_n; m=u.size(); A.resize(n); e.resize(m); 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); } DSU tr1(n); vector<ll> edges; for (ll i=0; i<m; i++){ if (tr1.get(e[i].ff)!=tr1.get(e[i].ss)){ edges.push_back(i); tr1.unite(e[i].ff, e[i].ss); } } ll ret = count_common_roads(edges); vector<ll> ans; for (auto i:edges){ ans.push_back(heavyedge(edges, i, ret)); } 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...