제출 #1197396

#제출 시각아이디문제언어결과실행 시간메모리
1197396adiyer자매 도시 (APIO20_swap)C++20
0 / 100
2096 ms14596 KiB
#pragma optimize ("g",on) #pragma GCC optimize("inline") #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC optimize ("03") #include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 11; int n, m, dx, dy; int p[MAXN]; bool was[MAXN]; vector < int > g[MAXN]; vector < pair < int, pair < int, int > > > reb; 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++) reb.push_back({W[i], {U[i], V[i]}}); sort(reb.begin(), reb.end()); } void dfs(int v){ was[v] = 1; for(int u : g[v]) if(!was[u] && (dx == u) + (dy == u) + (dx == v) + (dy == v) < 2) p[u] = v, dfs(u); } bool f(int x, int y, int till){ for(int i = 0; i < n; i++) g[i].clear(), was[i] = 0; for(int i = 0; i <= till; i++){ g[reb[i].second.first].push_back(reb[i].second.second); g[reb[i].second.second].push_back(reb[i].second.first); } dx = dy = -1, dfs(x); if(!was[y]) return 0; dx = y, dy = p[y]; int v = p[y]; while(v != x){ if(g[v].size() > 2) return 1; v = p[v]; } for(int i = 0; i < n; i++) was[i] = 0; dfs(x); return was[y]; } int getMinimumFuelCapacity(int X, int Y) { int l = 0, r = m; while(r - l > 1){ int md = (l + r) / 2; if(f(X, Y, md)) r = md; else l = md; } if(r == m) return -1; return reb[r].first; }
#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...