Submission #394583

#TimeUsernameProblemLanguageResultExecution timeMemory
394583SugardorjSwapping Cities (APIO20_swap)C++14
100 / 100
231 ms22992 KiB
//#include "swap.h" #include <bits/stdc++.h> using namespace std; int i,j,s,t; int a[261523],b[234567],l,r,tt,k,y,z,n,m,x; const int MAXN=123456; vector<int>te,so, hursh[212334],an; struct node { int endP[2], par, size, val;//*, deed oroi, hemjee, utga } comp[MAXN]; int wpar[MAXN], depth[MAXN];//deed oroitoigoo holbogdoh urt, gun vector <int> adj[MAXN];//hurshuud int root(int u) { while (comp[u].par >= 0) u = comp[u].par; return u;//odoogoor hamgiin deed undes } bool join(int u, int v, int w) {//u, v, oroinuudiig w utgaar holboh int x = root(u), y = root(v);//deed undsuudiig ni oloh if (x == y) {//holbogdson bol if (comp[x].val < 0) comp[x].val = w;//x ni utga avaagui bol w utgiig olgoh return false;// } if (comp[x].size < comp[y].size) { swap(x, y); swap(u, v);//ali olon oroitoi olonlogiig i u bolgoh } comp[x].size += comp[y].size; comp[y].par = x;//negtgeh, y-iin deed oroig x bolgoh wpar[y] = w; adj[x].push_back(y);//deed oroitoigoo holbogdoh urt w, xiin hursh y if (comp[x].val < 0 && comp[y].val < 0 && (u == comp[x].endP[0] || u == comp[x].endP[1]) && (v == comp[y].endP[0] || v == comp[y].endP[1])) { if (u == comp[x].endP[0]) comp[x].endP[0] = comp[x].endP[1]; if (v == comp[y].endP[0]) comp[x].endP[1] = comp[y].endP[1]; else comp[x].endP[1] = comp[y].endP[0]; } else if (comp[x].val < 0) comp[x].val = w; return true; } void DFS(int u) { for (int v : adj[u]) { depth[v] = depth[u] + 1; DFS(v);//guniig ni dfs ashiglaj oloh } } void init(int N, int M, vector <int> U, vector <int> V, vector <int> W) { vector <int> sorted(M); for (i = 0; i <M; i ++) sorted[i]=i; sort(sorted.begin(), sorted.end(),[&](int i, int j) {return W[i] < W[j];}); for (int i = 0; i < N; i++) { comp[i].endP[0] = comp[i].endP[1] = i; comp[i].par = -1; comp[i].size = 1; comp[i].val = -1; } for (int i : sorted) join(U[i], V[i], W[i]); for (int i = 0; i < N; i++) if (comp[i].par < 0) DFS(i); } int getMinimumFuelCapacity(int u, int v) { if (root(u) != root(v)) return -1; int res = 0; while (u != v) { if (depth[u] < depth[v]) swap(u, v); res = max(res, wpar[u]); u = comp[u].par; } while (u >= 0 && comp[u].val < 0) { res = max(res, wpar[u]); u = comp[u].par; } if (u < 0) return -1; return max(res, comp[u].val); }
#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...