이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
int anc[500010][21];
vector<pii> g[500010];
ll d[500010];
int tmp=0;
int ent[500010], ex[500010];
int n;
void dfs(int s){
tmp++;
ent[s]=tmp;
for(pii pr:g[s]){
int u=pr.ft, c=pr.sc;
if(u==anc[s][0]){continue;}
d[u]=d[s]+c;
anc[u][0]=s;
dfs(u);
}
tmp++;
ex[s]=tmp;
return;
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(int i=0; i<(n-1); i++){
g[A[i]+1 ].pb({B[i]+1, D[i]});
g[B[i]+1 ].pb({A[i]+1, D[i]});
}
dfs(1);
for(int i=1; i<=20; i++){
for(int j=1; j<=n; j++){
anc[j][i]=anc[anc[j][i-1] ][i-1];
}
}
return;
}
bool is_anc(int u, int v){
return (ent[u]<=ent[v]) && (ex[u]>=ex[v]);
}
int lca(int u, int v){
if( is_anc(u, v) ){
return u;
}
int cr=u;
for(int i=20; i>=0; i--){
if( (anc[cr][i]!=(0)) && (!is_anc(anc[cr][i], v)) ){
cr=anc[cr][i];
}
}
return anc[cr][0];
}
bool v[500010];
int mrk[5010];
ll d1[5010];
ll dfs0(int s){
ll res=1e18;
//cout<<"x"<<flush;
if(mrk[s]==1){
d1[s]=0;
}
else{
if(d1[s]==0){
d1[s]=1e18;}
}
//cout<<s<<" "<<mrk[s]<<" "<<d1[s]<<"\n";
v[s]=true;
for(pii pr:g[s]){
int u=pr.ft, c=pr.sc;
if(v[u]){continue;}
res=min(res, dfs0(u));
d1[s]=min(d1[u]+c, d1[s]);
}
v[s]=false;
if(s==1){
v[s]=true;
for(pii pr:g[s]){
int u=pr.ft, c=pr.sc;
if(v[u]){continue;}
d1[u]=min(d1[s]+c, d1[u]);
res=min(res, dfs0(u));
d1[s]=min(d1[u]+c, d1[s]);
}
v[s]=false;
}
if(mrk[s]==2){
res=min(res, d1[s]);
}
//return res;
return res;
}
long long Query(int S, int X[], int T, int Y[]) {
ll res=1e18;
if( n<=5000 ){
for(int i=0; i<S; i++){
mrk[X[i]+1 ]=1;
}
//ll res=1e18;
for(int i=0; i<T; i++){
mrk[Y[i]+1 ]=2;
}
//res=min(res, (dfs0(1)).ft);
ll r=dfs0(1);
res=min(res, r);
for(int i=0; i<S; i++){
mrk[X[i]+1 ]=0;
}
//ll res=1e18;
for(int i=0; i<T; i++){
mrk[Y[i]+1 ]=0;
}
for(int i=1;i<=n; i++){
d1[i]=0;
}
}
else{
for(int i=0; i<S; i++){
for(int j=0; j<T; j++){
int u=X[i]+1, v=Y[j]+1;
int anc=lca(u, v);
res=min(res, d[u]+d[v]-2*d[anc]);
}
}
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |