Submission #1226008

#TimeUsernameProblemLanguageResultExecution timeMemory
1226008Godgift42Swapping Cities (APIO20_swap)C++20
0 / 100
2096 ms8124 KiB
#include "swap.h" #include <bits/stdc++.h> #include <vector> using namespace std; vector<int> u; vector<int> v; vector<int> w; vector<pair<int,int>> sm; int n; int m; vector<int> rt; vector<int> sz; vector<int> fr; vector<int> jk; int find(int u){ if(rt[u]!=u){ int p=fr[u]; rt[u]=find(rt[u]); if(p or jk[u]>=3)fr[rt[u]]=1; } return rt[u]; } bool unite(int a, int b){ a=find(a); b=find(b); if(a==b){ fr[a]=1; return false; } if(sz[a]>=sz[b]){ sz[a]+=sz[b]; if(fr[b])fr[a]=1; rt[b]=a; } else{ sz[b]+=sz[a]; if(fr[a])fr[b]=1; rt[a]=b; } return true; } bool fk=false; void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) { u=U; v=V; w=W; n=N; m=M; vector<int> pl(n); if(m==n-1){ fk=true; for(int i=0;i<m;i++){ pl[u[i]]++; pl[v[i]]++; } for(auto i:pl){ if(i>=3)fk=false; } } for(int i=0;i<M;i++){ sm.push_back({w[i],i}); } sort(sm.begin(),sm.end()); fr.resize(n,0); sz.resize(n,1); jk.resize(n); rt.resize(n); } int getMinimumFuelCapacity(int X, int Y) { if(fk)return -1; for(int i=0;i<n;i++){ rt[i]=i; sz[i]=1; jk[0]; fr[i]=0; } int ans=0; for(int i=0;i<m;i++){ jk[u[sm[i].second]]++; jk[v[sm[i].second]]++; bool ko=unite(u[sm[i].second],v[sm[i].second]); ans=sm[i].first; if(find(X)==find(Y) and fr[find(X)])break; } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...