Submission #391544

#TimeUsernameProblemLanguageResultExecution timeMemory
391544Jarif_RahmanSwapping Cities (APIO20_swap)C++17
37 / 100
2082 ms12092 KiB
#include "swap.h" #include <bits/stdc++.h> #define pb push_back #define f first #define sc second using namespace std; typedef long long int ll; typedef string str; struct dsu{ int n; vector<int> sz, p; vector<bool> ok; vector<int> adj; dsu(int nn){ n = nn; sz.resize(n, 1); p.resize(n); ok.resize(n, 0); adj.resize(n, 0); for(int i = 0; i < n; i++) p[i] = i; } int get(int x){ if(p[x] != x) p[x] = get(p[x]); return p[x]; } void unite(int a, int b){ adj[a]++, adj[b]++; if(adj[a] >= 3) ok[get(a)] = 1; if(adj[b] >= 3) ok[get(b)] = 1; a = get(a), b = get(b); if(a == b){ ok[a] = 1; return; } if(sz[b] > sz[a]) swap(a, b); sz[a]+=sz[b]; sz[b] = 0; ok[a] = ok[a]|ok[b]; ok[b] = 0; p[b] = a; } }; int n, m; vector<tuple<int, int, int>> edges; void init(int n, int m, vector<int> u, vector<int>v, vector<int>w){ ::n = n, ::m = m; for(int i = 0; i < m; i++){ edges.pb({w[i], u[i], v[i]}); } sort(edges.begin(), edges.end()); } int getMinimumFuelCapacity(int X, int Y){ dsu ds(n); for(int i = 0; i < m; i++){ auto [w, a, b] = edges[i]; ds.unite(a, b); if(ds.get(X) == ds.get(Y) && ds.ok[ds.get(X)]) return w; } return -1; }
#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...