QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#217049 | #6101. Ring Road | ucup-team1004 | WA | 622ms | 58324kb | C++14 | 3.1kb | 2023-10-16 12:58:29 | 2023-10-16 12:58:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
if(x.empty())return out<<"[]";
out<<'['<<x[0];
for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
cerr<<x<<' ',debug(y...);
}
const int N=2e5+10;
const ll INF=1e18;
int n,m,k;
vector<pair<int,ll> >A[N],B[N];
vector<int>C[N],D[N];
void add(int u,int v,ll w,int op){
// if(op)debug(u,v,w);
if(op)C[u].push_back(v),C[v].push_back(u);
else D[u].push_back(v),D[v].push_back(u);
B[u].push_back({v,w}),B[v].push_back({u,w});
}
#define v e.first
#define w e.second
void build(int u,int fa=0){
int r=0;
for(auto e:A[u])if(v^fa){
build(v,u);
// debug(u,v,w,r);
add(++k,v,w,1);
if(r)add(k,r,0,1);
r=k;
}
if(r)add(u,r,0,1);
}
#undef v
#undef w
int rt,siz[N],mx[N],col[N],vis[N];
vector<int>id,cur;
void dfs1(int u,int fa=0){
siz[u]=1,cur.push_back(u);
for(int v:C[u])if(v^fa&&!vis[v]){
dfs1(v,u);
siz[u]+=siz[v];
}
}
void dfs2(int u,int cnt,int fa=0){
mx[u]=0;
for(int v:C[u])if(v^fa&&!vis[v]){
dfs2(v,cnt,u);
mx[u]=max(mx[u],siz[v]);
}
mx[u]=max(mx[u],cnt-siz[u]);
if(mx[u]<mx[rt])rt=u;
}
void dfs3(int u,int c,int fa){
col[u]=c;
for(int v:C[u])if(v^fa&&!vis[v]){
dfs3(v,c,u);
}
}
void dfs4(int u,int fa){
for(int v:D[u])if(col[v]&&col[u]!=col[v]){
if(u<v)id.push_back(u);
}
for(int v:C[u])if(v^fa&&!vis[v]){
dfs4(v,u);
}
}
void clr(int u,int fa){
col[u]=0;
for(int v:C[u])if(v^fa&&!vis[v]){
clr(v,u);
}
}
#define v e.first
#define w e.second
ll d[N],ans[N];
int is[N];
vector<pair<int,int> >o[N];
void dij(int s){
priority_queue<pair<ll,int> >q;
for(int x:cur)d[x]=INF,is[x]=0;
q.push({0,s}),d[s]=0;
for(int u;!q.empty();){
u=q.top().second,q.pop();
if(is[u])continue;
is[u]=1;
for(auto e:B[u]){
if(d[v]>d[u]+w){
d[v]=d[u]+w,q.push({-d[v],v});
}
}
}
// debug(cur,s);
for(int u:cur){
// debug(d[u]);
for(auto e:o[u])if(col[v]){
ans[w]=min(ans[w],d[u]+d[v]);
}
}
}
#undef v
#undef w
void solve(int u){
cur={};
rt=0,dfs1(u),dfs2(u,siz[u]),u=rt,vis[u]=1;
for(int v:C[u])if(!vis[v])dfs3(v,v,u);
id={u};
for(int v:C[u])if(!vis[v])dfs4(v,u);
for(int s:id)dij(s);
for(int x:cur)col[x]=0;
for(int v:C[u])if(!vis[v])solve(v);
}
int leaf[N];
int main(){
scanf("%d",&n),k=n;
for(int i=2,x;i<=n;i++){
ll w;
scanf("%d%lld",&x,&w);
A[x].push_back({i,w}),A[i].push_back({x,w});
leaf[x]=1;
}
vector<int>pos;
for(int i=1;i<=n;i++){
if(!leaf[i])pos.push_back(i);
}
for(int len=pos.size(),i=0;i<len;i++){
ll w;
scanf("%lld",&w);
add(pos[i],pos[(i+1)%len],w,0);
}
scanf("%d",&m);
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
o[u].push_back({v,i});
}
fill(ans+1,ans+1+m,INF);
mx[0]=n+1;
build(1),solve(1);
for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 34204kb
input:
4 1 9 1 8 1 0 9 9 9 6 1 2 1 3 1 4 2 3 2 4 3 4
output:
9 8 0 9 9 8
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 34136kb
input:
11 1 9 1 8 3 0 4 7 4 1 3 6 1 0 8 7 8 1 10 6 0 0 0 0 0 0 21 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 7 1 8 2 9 3 10 4 11 5 1 6 2 7 3 8 4 9 5 10 6 11
output:
7 8 8 7 7 7 0 7 1 7 7 7 1 7 0 7 0 8 1 6 0
result:
ok 21 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 34140kb
input:
11 1 9 1 8 3 0 4 7 4 1 3 6 1 0 8 7 8 1 10 6 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 1000000000000 21 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 7 1 8 2 9 3 10 4 11 5 1 6 2 7 3 8 4 9 5 10 6 11
output:
9 8 8 15 9 14 0 7 1 7 14 9 15 9 22 9 23 8 15 16 16
result:
ok 21 numbers
Test #4:
score: -100
Wrong Answer
time: 622ms
memory: 58324kb
input:
99998 1 683940 1 335116 3 198362 4 28825 5 625394 6 314200 7 270653 8 61629 9 650997 10 693039 11 159577 12 466708 13 715788 14 262771 15 615302 16 1457 17 650381 18 542652 19 101993 20 197937 21 474452 22 859631 23 327526 24 705522 25 500710 26 595050 27 577264 28 955258 29 269967 30 4012 31 471435...
output:
683940 335116 533478 562303 1187697 1501897 1772550 1834179 2485176 3178215 3337792 3804500 4520288 4783059 5398361 5399818 6050199 6592851 6694844 6892781 7367233 8226864 8554390 9259912 9760622 10355672 10932936 11888194 12158161 12162173 12633608 13385421 13746582 14637654 14649654 15558759 15771...
result:
wrong answer 40th numbers differ - expected: '17564334', found: '18932214'