| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 657843 | activedeltorre | 자매 도시 (APIO20_swap) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "swap.h"
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
//ifstream cin("a.in");
//ofstream cout("a.out");
vector<pair<long long,pair<long long,long long> > >edges;
bool cmp(pair<long long,pair<long long,long long> >a,pair<long long,pair<long long,long long> >b)
{
return a.first<b.first;
}
vector<pair<long long,long long> >adj[200005];
vector<long long>vec;
long long rasp[200005];
long long jos[200005];
long long sus[200005];
long long lvl[200005];
long long inf=1e14;
void dfs(long long curr,long long parent)
{
long long i,k;
lvl[curr]=lvl[parent]+1;
vec.clear();
if(adj[curr].size()>=3)
{
for(i=0; i<adj[curr].size(); i++)
{
vec.push_back(adj[curr][i].second);
}
sort(vec.begin(),vec.end());
jos[curr]=vec[2];
}
else
{
jos[curr]=inf;
}
for(i=0; i<adj[curr].size(); i++)
{
k=adj[curr][i].first;
if(k!=parent)
{
dfs(k,curr);
}
jos[curr]=min(jos[curr],max(jos[curr],adj[curr][i].second));
}
}
void dfs2(long long curr,long long par,long long val)
{
long long i,k;
sus[curr]=max(min(jos[par],sus[par]),val);
rasp[curr]=min(sus[curr],jos[curr]);
for(i=0; i<adj[curr].size(); i++)
{
k=adj[curr][i].first;
if(k!=par)
{
dfs2(k,curr,adj[curr][i].second);
}
}
}
///bl e parinte
/// drum e cost de a merge la parinte
/// ext e cost minim degreee 3
long long bl[33][100005];
long long ext[33][100005];
long long drum[33][100005];
void dfs3(long long curr,long long par,long long val)
{
long long i,k;
bl[0][curr]=par;
ext[0][curr]=min(rasp[par],rasp[curr]);
drum[0][curr]=val;
for(i=1; i<=30; i++)
{
bl[i][curr]=bl[i-1][bl[i-1][curr]];
ext[i][curr]=min(ext[i-1][curr],ext[i-1][bl[i-1][curr]]);
drum[i][curr]=max(drum[i-1][curr],drum[i-1][bl[i-1][curr]]);
}
for(i=0; i<adj[curr].size(); i++)
{
k=adj[curr][i].first;
if(k!=par)
{
dfs3(k,curr,adj[curr][i].second);
}
}
}
long long lca (long long a,long long b)
{
long long i,curr;
if(lvl[a]<lvl[b])
{
swap(a,b);
}
for(i=30; i>=0; i--)
{
curr=bl[i][a];
if(lvl[curr]>=lvl[b])
{
a=curr;
}
}
if(a==b)
{
return a;
}
else
{
for(i=30; i>=0; i--)
{
if(bl[i][a]!=bl[i][b])
{
a=bl[i][a];
b=bl[i][b];
}
}
return bl[0][a];
}
}
pair<long long,long long> calc (long long a,long long b)
{
long long curr,maxdrum=0,minrel=inf,i;
for(i=30; i>=0; i--)
{
curr=bl[i][a];
if(lvl[curr]>=lvl[b])
{
maxdrum=max(maxdrum,drum[i][a]);
minrel=min(minrel,ext[i][a]);
a=curr;
}
}
return make_pair(maxdrum,minrel);
}
void init(long long n, long long m,vector<long long> a, vector<long long> b, vector<long long> w)
{
long long i;
for(i=1; i<=m; i++)
{
// a[i-1]++;
// b[i-1]++;
adj[a[i-1]].push_back({b[i-1],w[i-1]});
adj[b[i-1]].push_back({a[i-1],w[i-1]});
// edges.push_back({w[i-1],{a[i-1],b[i-1]}});
}
// sort(edges.begin(),edges.end(),cmp);
sus[0]=inf;
jos[0]=inf;
dfs(1,0);
dfs2(1,0,0);
dfs3(1,0,0);
}
long long getMinimumFuelCapacity(long long x, long long y)
{
long long lc;
//x++;
// y++;
pair<long long,long long>a;
pair<long long,long long>b;
lc=lca(x,y);
a=calc(x,lc);
b=calc(y,lc);
a.first=max(a.first,b.first);
a.second=min(a.second,b.second);
a.first=max(a.first,b.second);
if(a.first==inf)
{
return -1;
}
else
{
return a.first;
}
}
/*int main()
{
long long N, M;
cin>>N>>M;
vector<long long> U(M), V(M), W(M);
for (long long i = 0; i < M; ++i)
{
cin>>U[i]>>V[i]>>W[i];
}
long long Q;
cin>>Q;
vector<long long> X(Q), Y(Q);
for (long long i = 0; i < Q; ++i)
{
cin>>X[i]>>Y[i];
}
init(N, M, U, V, W);
vector<long long> minimum_fuel_capacities(Q);
for (long long i = 0; i < Q; ++i)
{
minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
}
for (long long i = 0; i < Q; ++i)
{
cout<<minimum_fuel_capacities[i]<<'\n';
}
return 0;
}*/