QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#218611#6101. Ring Road275307894aTL 4ms43060kbC++142.8kb2023-10-18 15:51:262023-10-18 15:51:26

Judging History

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

  • [2023-10-18 15:51:26]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:43060kb
  • [2023-10-18 15:51:26]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__uint128_t;
const int N=3e5+5,M=N*8+5,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-6;const int INF=1e9+7;mt19937 rnd(263082);
int n,m,fa[N];ll w[N];vector<pair<int,ll> > S[N];vector<int> G[N],son[N];
vector<pii> q[N];ll ans[N];
void con(int x,int y){S[x].eb(y,w[y]);S[y].eb(x,w[y]);G[x].eb(y);G[y].eb(x);}
void reb(vector<int> son,int x){
	if(son.empty()) return;
	if(son.size()==1) {con(x,son.back());return;}
	int v=++m,Le=son.size()/2;con(x,v);
	vector<int> ls(son.begin(),son.begin()+Le),rs(son.begin()+Le,son.end());
	reb(ls,m);reb(rs,m);
}
int Ct,f[N],siz[N],vis[N],col[N],Rt;
ll d[N];
vector<int> scc;
void dij(int x){
	for(int i:scc) d[i]=1e18;d[x]=0;
	priority_queue<pair<ll,int> > Q;Q.emplace(0,x);
	while(!Q.empty()){
		auto p=Q.top();Q.pop();p.fi*=-1;if(p.fi^d[p.se]) continue;
		for(auto i:S[p.se]) if(d[i.fi]>i.se+p.fi) d[i.fi]=i.se+p.fi,Q.emplace(-d[i.fi],i.fi);
	}
	for(int i:scc) for(auto j:q[i]) if(col[j.fi]==col[i]) ans[j.se]=min(ans[j.se],d[i]+d[j.fi]);
}
void GI(int x,int La){scc.eb(x);siz[x]=1;col[x]=Rt;for(int i:G[x]) if(i^La&&!vis[i]) GI(i,x),siz[x]+=siz[i];}
void DP(int x,int La){f[x]=Ct-siz[x];for(int i:G[x]) if(i^La&&!vis[i]) f[x]=max(f[x],siz[i]),DP(i,x);if(f[Rt]>f[x]) Rt=x;}
pii search(int x,int La){
	if(son[x].empty()&&x<=n) return make_pair(x,x); 
	pii ans=make_pair(INF,-INF);
	for(int i:G[x]) if(!vis[i]&&i^La) {auto p=search(i,x);ans.fi=min(ans.fi,p.fi);ans.se=max(ans.se,p.se);}
	return ans;
}
void dfs(int x){
	Rt=x;GI(x,0);Ct=siz[x];f[Rt=0]=INF;DP(x,0);vis[x=Rt]=1;assert(f[x]*2<=Ct);
	dij(x);assert(G[x].size()<=3);
	for(int i:G[x]) if(!vis[i]) {
		auto p=search(i,x);
		if(p.fi<=n) dij(p.fi);
		if(p.se>p.fi) dij(p.se);
	}
	for(int i:G[x]) if(!vis[i]) dfs(i);
}
void Solve(){
	int i,j;scanf("%d",&n);
	for(i=2;i<=n;i++) scanf("%d%lld",&fa[i],&w[i]),son[fa[i]].eb(i);
	m=n;for(i=1;i<=n;i++) reb(son[i],i);
	vector<int> leaf;
	for(i=1;i<=n;i++) if(son[i].empty()) leaf.eb(i);leaf.eb(leaf.front());
	for(i=1;i<leaf.size();i++) {ll y;scanf("%lld",&y);S[leaf[i]].eb(leaf[i-1],y);S[leaf[i-1]].eb(leaf[i],y);}
	int Q;scanf("%d",&Q);for(i=1;i<=Q;i++){int x,y;scanf("%d%d",&x,&y);q[x].eb(y,i);q[y].eb(x,i);ans[i]=1e18;}
	dfs(1);for(i=1;i<=Q;i++) printf("%lld\n",ans[i]);
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 40880kb

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: 4ms
memory: 43060kb

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: 3ms
memory: 40844kb

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
Time Limit Exceeded

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:


result: