이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
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);
}
ff(i,0,n) dp[i]=mod;
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);
}
/*
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |