제출 #1191683

#제출 시각아이디문제언어결과실행 시간메모리
1191683lovrotSwapping Cities (APIO20_swap)C++20
37 / 100
2094 ms15008 KiB
#include "swap.h" #include <cstdio> #include <cstring> #include <vector> #include <algorithm> #define PB push_back #define X first #define Y second using namespace std; typedef pair<int, int> pii; const int N = 1e5 + 10; const int OO = 1e9 + 10; vector<pii> g[N]; void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) { for(int i = 0; i < m; ++i) { g[U[i]].PB({V[i], W[i]}); g[V[i]].PB({U[i], W[i]}); } } int bio[N], sum, siz, tri; void dfs(int u, int k) { if(bio[u]) return; bio[u] = 1; siz ++; int cnt = 0; for(pii e : g[u]) { if(e.Y <= k) { dfs(e.X, k); sum ++; cnt ++; } } tri = max(tri, cnt); } int getMinimumFuelCapacity(int X, int Y) { int lo = -1, hi = OO; for(int mi = (lo + hi) / 2; hi - lo > 1; mi = (lo + hi) / 2) { memset(bio, 0, sizeof(bio)); sum = 0; siz = 0; tri = 0; dfs(X, mi); if((tri >= 3 || siz <= sum / 2) && bio[Y]) { hi = mi; } else { lo = mi; } } return hi == OO ? -1 : hi; }
#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...