제출 #725232

#제출 시각아이디문제언어결과실행 시간메모리
725232n0sk1ll자매 도시 (APIO20_swap)C++14
7 / 100
407 ms40000 KiB
#include <bits/stdc++.h> #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0) #define mp make_pair #define xx first #define yy second #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define all(x) x.begin(),x.end() #define ff(i,a,b) for (int i = a; i < b; i++) #define fff(i,a,b) for (int i = a; i <= b; i++) #define bff(i,a,b) for (int i = b-1; i >= a; i--) #define bfff(i,a,b) for (int i = b; i >= a; i--) using namespace std; long double typedef ld; unsigned int typedef ui; long long int typedef li; pair<int,int> typedef pii; pair<li,li> typedef pli; pair<ld,ld> typedef pld; vector<vector<int>> typedef graph; unsigned long long int typedef ull; //const int mod = 998244353; const int mod = 1000000007; //Note to self: Check for overflow #include "swap.h" namespace dsu { int up[100005]; void build(int n) { ff(i,0,n) up[i]=-1; } int Up(int x) { if (up[x]<0) return x; return up[x]=Up(up[x]); } void dsu(int a, int b) { a=Up(a),b=Up(b); if (a==b) return; if (up[a]<up[b]) swap(a,b); up[b]+=up[a],up[a]=b; } } //kad nadjemo spanning tree: vector<vector<pii>> g(100005); int tin[100005],tout[100005]; int up[17][100005],we[17][100005],twe[17][100005]; int dp[100005]; //min twe u subtree int VREME=0; void dfs(int p, int q, int qw) { tin[p]=++VREME,up[0][p]=q,we[0][p]=qw; for (auto [it,w] : g[p]) if (it!=q) dfs(it,p,w); tout[p]=VREME; } void tfs(int p, int q) { dp[p]=min(dp[p],twe[0][p]); for (auto [it,w] : g[p]) if (it!=q) { tfs(it,p); dp[p]=min(dp[p],max(w,dp[it])); } } void build(int n) { ff(i,0,n) { vector<int> temp; for (auto [it,w] : g[i]) temp.pb(w); if ((int)temp.size()<3) twe[0][i]=mod; else sort(all(temp)),twe[0][i]=temp[2]; } ff(k,1,17) ff(i,0,n) { up[k][i]=up[k-1][up[k-1][i]]; we[k][i]=max(we[k-1][i],we[k-1][up[k-1][i]]); twe[k][i]=min(twe[k-1][i],twe[k-1][up[k-1][i]]); } } bool anc(int a, int b) { return tin[a]<=tin[b] && tout[a]>=tout[b]; } int Lca(int a, int b, int &maxput, int &mintwe) { bff(k,0,17) if (!anc(up[k][a],b)) { mintwe=min(mintwe,twe[k][a]); maxput=max(maxput,we[k][a]); a=up[k][a]; } bff(k,0,17) if (!anc(up[k][b],a)) { mintwe=min(mintwe,twe[k][b]); maxput=max(maxput,we[k][b]); b=up[k][b]; } if (anc(b,a)) swap(a,b); if (anc(a,b)) { mintwe=min(mintwe,twe[0][b]); maxput=max(maxput,we[0][b]); mintwe=min(mintwe,twe[0][a]); return a; } mintwe=min(mintwe,twe[0][b]); mintwe=min(mintwe,twe[0][a]); maxput=max(maxput,we[0][a]); maxput=max(maxput,we[0][b]); a=up[0][a]; mintwe=min(mintwe,twe[0][a]); return a; } void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) { vector<pair<int,pii>> sorta; ff(i,0,m) sorta.pb({w[i],{u[i],v[i]}}); sort(all(sorta)); vector<pair<int,pii>> izdajnici; dsu::build(n); for (auto it : sorta) { int a=it.yy.xx,b=it.yy.yy; int pa=dsu::Up(a),pb=dsu::Up(b); if (pa!=pb) g[a].pb({b,it.xx}),g[b].pb({a,it.xx}),dsu::dsu(pa,pb); else izdajnici.pb(it); } dfs(0,0,0); build(n); ff(i,0,n) dp[i]=mod; for (auto it : izdajnici) { int nebitno=-1; int a=it.yy.xx,b=it.yy.yy,w=it.xx; int c=Lca(a,b,nebitno,nebitno); dp[c]=min(dp[c],w); } tfs(0,0); } int getMinimumFuelCapacity(int a, int b) { int maxput=0,spas=mod; int c=Lca(a,b,maxput,spas); spas=min(spas,dp[c]); if (spas==mod) return -1; return max(maxput,spas); } /* 4 4 0 1 1 1 2 2 2 3 3 3 0 4 4 0 1 1 2 2 3 3 0 5 4 0 1 1 1 2 1 2 3 1 3 4 1 10 0 1 0 2 0 3 0 4 1 2 1 3 1 4 2 3 2 4 3 4 5 6 0 1 4 0 2 4 1 2 1 1 3 2 1 4 10 2 3 3 3 1 2 2 4 0 1 3 2 0 1 5 0 2 5 1 1 2 11 10 0 1 5 1 2 4 2 3 3 2 4 10 1 5 1 5 6 2 5 7 2 0 8 10 8 9 1 8 10 1 10 1 0 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 */

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

swap.cpp: In function 'void dfs(int, int, int)':
swap.cpp:73:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for (auto [it,w] : g[p]) if (it!=q) dfs(it,p,w);
      |               ^
swap.cpp: In function 'void tfs(int, int)':
swap.cpp:80:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |     for (auto [it,w] : g[p]) if (it!=q)
      |               ^
swap.cpp: In function 'void build(int)':
swap.cpp:92:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |         for (auto [it,w] : g[i]) temp.pb(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...