Submission #981690

#TimeUsernameProblemLanguageResultExecution timeMemory
981690Alkaser_IDSwapping Cities (APIO20_swap)C++17
37 / 100
2041 ms13512 KiB
#include "swap.h" using namespace std; #include <bits/stdc++.h> int n,m; vector<pair<int,pair<int,int>>> v; void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) { n=N;m = M; for(int i=0;i<m;++i){ v.push_back({W[i],{U[i],V[i]}}); } sort(v.begin(),v.end()); } int p[100005],sz[100005],dg[100005]; bool bl[100005]; inline int parent(int a){ if(a == p[a]) return a; return a = parent(p[a]); } inline void merg(int x,int y){ int a = parent(x),b = parent(y); if(a == b) return; if(sz[b] > sz[a]) swap(a,b); sz[a] += sz[b]; p[b] = a; bl[a] = bl[a] | bl[b]; } int getMinimumFuelCapacity(int X, int Y) { for(int i=0;i<n;++i) { p[i] = i; sz[i] = 1; dg[i] = 0; bl[i] = false; } int res = -1; for(int i=0;i<m;++i){ int vl = v[i].first; int u = v[i].second.first, d = v[i].second.second; dg[u]++;dg[d]++; int U = parent(u),D = parent(d); if(dg[u] > 2) bl[U] = true; if(dg[d] > 2) bl[D] = true; if(U == D) bl[U] = true; else merg(U,D); int px = parent(X),py = parent(Y); if(px == py && bl[px]) { res = vl; break; } } return res; }
#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...