Submission #466339

#TimeUsernameProblemLanguageResultExecution timeMemory
466339MohamedAliSaidaneIslands (IOI08_islands)C++14
24 / 100
541 ms55124 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ld,ld> pld; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pii> vpi; #define pb push_back #define popb pop_back #define all(v) (v).begin(),(v).end() #define ff first #define ss second const int MOD = 1e9 + 7; const ll INF = 1e18; vi p, rnk, setsz; int n; int findset(int i){ return p[i] == i? i: findset(p[i]);} void unite(int i, int j) { if(findset(i) == findset(j)) return; int x= findset(i); int y = findset(j); if(rnk[x] > rnk[y]) swap(x,y); p[x] = y; if(rnk[x] == rnk[y]) rnk[y] ++; setsz[y] += setsz[x]; return; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); vector<pair<ll,pll>> edges; cin >> n; int deg[n+1]; memset(deg,0,sizeof(deg)); p.assign(n+1,0); rnk.assign(n+1,0); setsz.assign(n+1,1); for(ll i = 1; i <=n; i ++) { p[i-1] = i-1; ll u, dist; cin >> u >> dist; edges.pb({dist,{i,u}}); } sort(all(edges)); reverse(all(edges)); ll ans = 0; for(int j = 0; j < n; j ++) { ll d = edges[j].ff; ll u = edges[j].ss.ff - 1; ll v = edges[j].ss.ss - 1; if(findset(u) == findset(v)) continue; else if(deg[u] < 2 && deg[v] < 2) { deg[u] ++; deg[v] ++; ans += d; unite(u,v); } } cout << ans << '\n'; } /* Sample test case: 7 3 8 7 2 4 2 1 4 1 9 3 4 2 3 */
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...