제출 #291693

#제출 시각아이디문제언어결과실행 시간메모리
291693nvmdava자매 도시 (APIO20_swap)C++17
100 / 100
431 ms31768 KiB
#include "swap.h" #include <bits/stdc++.h> using namespace std; const int N = 100005; const int INF = 1000000005; #define ff first #define ss second vector<pair<int, pair<int, int> > > edge; vector<pair<int, int> > dsu[N]; int ans[N]; int d[N]; vector<int> gr[N]; void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) { cerr<<"BEGIN"; for(int i = 0; i < N; ++i) ans[i] = INF; for(int i = 0; i < N; ++i){ dsu[i].push_back({0, i}); gr[i].push_back(i); } for(int i = 0; i < M; ++i) edge.push_back({W[i], {V[i], U[i]}}); sort(edge.begin(), edge.end()); for(auto& wtf : edge){ int v = wtf.ss.ff; int u = wtf.ss.ss; int w = wtf.ff; int vv = dsu[v].back().ss; int uu = dsu[u].back().ss; if(vv == uu){ ans[vv] = min(ans[vv], w); continue; } ++d[v]; ++d[u]; if(gr[vv].size() > gr[uu].size()){ swap(vv, uu); swap(v, u); } ans[uu] = min(ans[uu], max(w, ans[vv])); if(d[v] >= 3 || d[u] >= 3){ ans[uu] = min(ans[uu], w); } for(auto& x : gr[vv]){ gr[uu].push_back(x); dsu[x].push_back({w, uu}); } } } int getMinimumFuelCapacity(int x, int y){ int ix = dsu[x].size() - 1; int iy = dsu[y].size() - 1; int w = INF, mn = INF; while(ix >= 0 && iy >= 0 && dsu[x][ix].ss == dsu[y][iy].ss){ w = max(dsu[x][ix].ff, dsu[y][iy].ff); mn = min(mn, max(w, ans[dsu[x][ix].ss])); --ix; --iy; } w = max(w, mn); return (w == INF ? -1 : w); }
#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...