QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#217048 | #6101. Ring Road | ucup-team1004 | WA | 3ms | 35060kb | C++14 | 3.1kb | 2023-10-16 12:57:32 | 2023-10-16 12:57:32 |
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,int 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: 0ms
memory: 34748kb
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: 3ms
memory: 34716kb
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: -100
Wrong Answer
time: 0ms
memory: 35060kb
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:
-8001179633 -7273799670 -7273799670 -8001179639 -8001179633 -8001179639 -7273799662 -7273799655 -7273799661 -7273799655 -8001179639 -8001179633 -7273799663 -7273799669 -8728559602 -8001179633 -8001179648 -7273799670 -7273799663 -8001179638 -8001179634
result:
wrong answer 1st numbers differ - expected: '9', found: '-8001179633'