QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#217049#6101. Ring Roaducup-team1004WA 622ms58324kbC++143.1kb2023-10-16 12:58:292023-10-16 12:58:30

Judging History

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

  • [2023-10-16 12:58:30]
  • 评测
  • 测评结果:WA
  • 用时:622ms
  • 内存:58324kb
  • [2023-10-16 12:58:29]
  • 提交

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;
}

详细

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'