QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#217048#6101. Ring Roaducup-team1004WA 3ms35060kbC++143.1kb2023-10-16 12:57:322023-10-16 12:57:32

Judging History

你现在查看的是最新测评结果

  • [2023-10-16 12:57:32]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:35060kb
  • [2023-10-16 12:57:32]
  • 提交

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'