Submission #1199094

#TimeUsernameProblemLanguageResultExecution timeMemory
1199094GraySwapping Cities (APIO20_swap)C++20
17 / 100
2094 ms22600 KiB
#include "swap.h" #pragma GCC optimize("unroll-loops,Ofast") #include <bits/stdc++.h> #define ll int #define ln "\n" using namespace std; ll n, m; vector<array<ll, 3>> e; vector<ll> enabled; vector<vector<ll>> A; void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) { n=N; m=M; A.resize(n); e.resize(m); for (ll i=0; i<m; i++){ e[i] = {U[i], V[i], W[i]}; A[U[i]].push_back(i); A[V[i]].push_back(i); } } void dfs(ll u, ll to, vector<ll> &vis, ll &cnt1, ll &cnt2, ll &apos, ll &req){ vis[u]=1; cnt1++; ll cct=0; if (u==to) req=1; for (auto i:A[u]){ ll v = e[i][0]^e[i][1]^u; if (!enabled[i]) continue; cnt2++; cct++; if (!vis[v]) dfs(v, to, vis, cnt1, cnt2, apos, req); } if (cct>=3) apos=1; } int getMinimumFuelCapacity(int X, int Y) { ll l=0, r=2e9; vector<ll> vis(n); while (l+1<r){ ll mid = l+(r-l)/2; enabled.assign(m, 0); vis.assign(n, 0); for (ll i=0; i<m; i++){ if (e[i][2]<=mid) enabled[i]=1; } vis.assign(n, 0); ll cnt1=0, cnt2=0, pos1=0, pos2=0; dfs(X, Y, vis, cnt1, cnt2, pos1, pos2); if (pos2 and (pos1 or (cnt2/2>=cnt1))){ r=mid; }else l=mid; } return (r==2e9?-1:r); }
#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...