제출 #303251

#제출 시각아이디문제언어결과실행 시간메모리
303251nafis_shifatSwapping Cities (APIO20_swap)C++14
100 / 100
521 ms31672 KiB
#include "swap.h" #include<bits/stdc++.h> #define pii pair<int,int> using namespace std; const int mxn=2e5+1; const int inf=2e9; int L[mxn],R[mxn],cost[mxn]; int n,m; vector<int> sorted; struct reachability_tree { int par[mxn]; int lineW[mxn]; int sz[mxn]; int start[mxn]; int end[mxn]; int pw[mxn]; vector<int> w[mxn]; vector<int> li[mxn]; void init(int n) { for(int j=0;j<n;j++) { sz[j]=1; par[j]=j; start[j]=j; end[j]=j; lineW[j]=inf; } } int findrep(int u) { return par[u]==u ? u : findrep(par[u]); } void join(int u,int v,int weight) { int _u=findrep(u); int _v=findrep(v); if(_u==_v) { lineW[_u]=min(lineW[_u],weight); w[_u].push_back(weight); li[_u].push_back(lineW[_u]); return; } if(sz[_u]>sz[_v]) { swap(_u,_v); swap(u,v); } par[_u]=_v; sz[_v]+=sz[_u]; pw[_u]=weight; lineW[_v]=min(lineW[_v],lineW[_u]); if(lineW[_v]==inf && ((u==start[_u] || u==end[_u]) && (v==start[_v] || v==end[_v]))) { if(v==start[_v]) { start[_v]=end[_v]; end[_v]=start[_u] ^ end[_u] ^ u; } else { end[_v]=start[_u] ^ end[_u] ^ u; } } else { lineW[_v]=min(lineW[_v],weight); } w[_v].push_back(weight); li[_v].push_back(lineW[_v]); } int goup(int u,int weight) { while(par[u]!=u && pw[u]<=weight) { u=par[u]; } return u; } bool check(int x,int weight) { int k=upper_bound(w[x].begin(),w[x].end(),weight)-w[x].begin(); if(k==0) return false; int v=li[x][k-1]; return v<=weight; } } rt; 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++) { L[i]=U[i]; R[i]=V[i]; cost[i]=W[i]; sorted.push_back(i); } sort(sorted.begin(),sorted.end(),[](int a,int b) { return cost[a]<cost[b]; }); rt.init(n); for(int i=0;i<m;i++) { int u=L[sorted[i]]; int v=R[sorted[i]]; int c=cost[sorted[i]]; rt.join(u,v,c); } } int getMinimumFuelCapacity(int X, int Y) { int lo=0; int hi=m-1; int ans=-1; while(lo<=hi) { int m=lo+hi>>1; int v=cost[sorted[m]]; int a=rt.goup(X,v); int b=rt.goup(Y,v); if(a==b && rt.check(a,v)) { ans=v; hi=m-1; } else { lo=m+1; } } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:144:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  144 |   int m=lo+hi>>1;
      |         ~~^~~
#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...