이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "factories.h"
#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define en cin.close();return 0;
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N = 5e5+5;
const int LOG = log2(N)+2;
vector<pair<int,int> > g[N];
vector<pair<int,ll> > g2[N];
int par[N][LOG];
int tin[N], tout[N], tt;
int col[N];
ll dist[N], mindist;
void dfs(int u, int p)
{
tin[u]=++tt;
par[u][0]=p;
for(int i = 1;i<LOG;i++)
par[u][i]=par[par[u][i-1]][i-1];
for(auto v:g[u])
if(v.fi!=p)
dist[v.fi]=dist[u]+v.se,
dfs(v.fi,u);
tout[u]=tt;
}
bool isanc(int u, int v)
{
return (tin[u]<=tin[v]&&tout[v]<=tout[u]);
}
int lca(int u, int v)
{
if(isanc(u,v))
return u;
if(isanc(v,u))
return v;
for(int i = LOG-1;i>=0;i--)
if(!isanc(par[u][i],v))
u=par[u][i];
return par[u][0];
}
void Init(int n, int a[], int b[], int d[])
{
for(int i = 0;i<n-1;i++)
g[a[i]].pb({b[i],d[i]}),
g[b[i]].pb({a[i],d[i]});
dfs(0,0);
}
void con(int u, int v)
{
if(u==v)
return;
ll d = abs(dist[u]-dist[v]);
g2[u].pb({v,d});
g2[v].pb({u,d});
}
int createvt(vector<int> &nodes)
{
sort(nodes.begin(),nodes.end(),[](int &i, int &j){return (tin[i]<tin[j]);});
for(int i = (int)(nodes.size())-2;i>=0;i--)
nodes.pb(lca(nodes[i],nodes[i+1]));
sort(nodes.begin(),nodes.end(),[](int &i, int &j){return (tin[i]<tin[j]);});
vector<int> ve;
ve.pb(nodes[0]);
for(int i = 1;i<nodes.size();i++)
{
while(!isanc(ve.back(),nodes[i]))
con(ve.back(),ve[ve.size()-2]),
ve.pop_back();
ve.pb(nodes[i]);
}
while(ve.size()>1)
con(ve.back(),ve[ve.size()-2]),
ve.pop_back();
return ve[0];
}
pair<ll,ll> dfs2(int u, int p)
{
ll min1 = 1e18, min2 = 1e18;
if(col[u]==1)
min1=0;
else if(col[u]==2)
min2=0;
for(auto v:g[u])
{
if(v.fi!=p)
{
pair<ll,ll> t = dfs2(v.fi,u);
min1=min(min1,t.fi+v.se);
min2=min(min2,t.se+v.se);
}
}
mindist=min(mindist,min1+min2);
return {min1,min2};
}
long long Query(int n, int x[], int m, int y[])
{
vector<int> nodes;
for(int i = 0;i<n;i++)
nodes.pb(x[i]),
col[x[i]]=1;
for(int i = 0;i<m;i++)
nodes.pb(y[i]),
col[y[i]]=2;
int r = createvt(nodes);
mindist = 1e18;
dfs2(r,r);
for(auto x:nodes)
g2[x].clear(),
col[x]=0;
return mindist;
}
컴파일 시 표준 에러 (stderr) 메시지
factories.cpp: In function 'int createvt(std::vector<int>&)':
factories.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for(int i = 1;i<nodes.size();i++)
| ~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |