QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300845#6101. Ring RoadPhantomThresholdWA 229ms46296kbC++204.2kb2024-01-08 21:50:002024-01-08 21:50:00

Judging History

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

  • [2024-01-08 21:50:00]
  • 评测
  • 测评结果:WA
  • 用时:229ms
  • 内存:46296kb
  • [2024-01-08 21:50:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll inf=1e18;
int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin>>n;
	vector<vector<int>> T(n+n+5);
	vector<vector<pair<int,ll>>> tmp(n+n+5),G(n+n+5);
	auto addedge=[&](int u,int v,ll w,int ty=1)
	{
//		cerr<<"addedge "<<u<<' '<<v<<' '<<w<<endl;
		G[u].emplace_back(v,w);
		G[v].emplace_back(u,w);
		if(ty)
		{
			T[u].push_back(v);
			T[v].push_back(u);
		}
	};
	for(int i=2;i<=n;i++)
	{
		int p;
		ll c;
		cin>>p>>c;
		tmp[p].emplace_back(i,c);
	}
	vector<int> lf;
	int ind=n;
	for(int i=1;i<=n;i++)
	{
//		cerr<<"split "<<i<<' '<<tmp[i].size()<<endl;
		if(tmp[i].empty())lf.push_back(i);
		else
		{
			int now=i;
			while(tmp[i].size()>2u)
			{
				auto [v,w]=tmp[i].back();
				tmp[i].pop_back();
				addedge(now,v,w);
				addedge(now,++ind,0);
				now=ind;
			}
			addedge(now,tmp[i][0].first,tmp[i][0].second);
			if(tmp[i].size()>1u)addedge(now,tmp[i][1].first,tmp[i][1].second);
		}
	}
	n=ind;
	int lcnt=(int)lf.size();
	for(int i=0;i<lcnt;i++)
	{
		ll c;
		cin>>c;
		addedge(lf[i],lf[(i+1)%lcnt],c,0);
	}
//	cerr<<"read graph end"<<endl;
	int q;
	cin>>q;
	vector<ll> ans(q+5,inf);
	vector<tuple<int,int,int>> qu;
	for(int i=1;i<=q;i++)
	{
		int u,v;
		cin>>u>>v;
		qu.emplace_back(u,v,i);
	}
	vector<ll> dis(n+5,inf);
	vector<int> good(n+5);
	auto dijk=[&](int s,int fl)
	{
		priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
		dis[s]=0;
		pq.emplace(0,s);
		while(not pq.empty())
		{
			auto [d,u]=pq.top();pq.pop();
			if(dis[u]!=d)continue;
			for(auto [v,w]:G[u])
			{
				if(good[v]==fl and dis[v]>dis[u]+w)
				{
					dis[v]=dis[u]+w;
					pq.emplace(dis[v],v);
				}
			}
		}
	};
	auto deledge=[&](int u,int v)
	{
//		cerr<<"delete edge "<<u<<' '<<v<<endl;
		for(auto it=G[u].begin();it!=G[u].end();++it)
		{
			if(it->first==v)
			{
				G[u].erase(it);
				break;
			}
		}
		for(auto it=G[v].begin();it!=G[v].end();++it)
		{
			if(it->first==u)
			{
				G[v].erase(it);
				break;
			}
		}
	};
	dijk(lf[0],0);
	for(auto [u,v,id]:qu)
	{
		ans[id]=min(ans[id],dis[u]+dis[v]);
	}
	deledge(lf[0],lf[lcnt-1]);
	
	vector<int> used(n+5),siz(n+5),mxson(n+5),vis(n+5),bel(n+5);
	vector<int> subs;
	int gcnt=0;
	function<void(int)> dfs0=[&](int u)
	{
//		cerr<<"dfs0 "<<u<<endl;
		siz[u]=1;mxson[u]=0;
		vis[u]=1;
		subs.push_back(u);
		for(auto v:T[u])
		{
			if(not used[v] and not vis[v])
			{
				dfs0(v);
				siz[u]+=siz[v];
				if(siz[v]>siz[mxson[u]])
					mxson[u]=v;
			}
		}
	};
	function<void(int,int)> dfs1=[&](int r,int u)
	{
		siz[u]=1;mxson[u]=0;
		vis[u]=0;
		for(auto v:T[u])
		{
			if(not used[v] and vis[v])
			{
				if(u==r)bel[v]=v;
				else bel[v]=bel[u];
				dfs1(r,v);
				siz[u]+=siz[v];
			}
		}
	};
	function<void(int,vector<tuple<int,int,int>>)> Divide=[&](int u,vector<tuple<int,int,int>> curq)
	{
//		cerr<<"Divide "<<u<<endl;
		subs.clear();
		dfs0(u);
		int r=u,sz=siz[u];
//		cerr<<"go "<<r<<' '<<siz[r]<<' '<<mxson[r]<<' '<<siz[mxson[r]]<<endl;
		while(mxson[r] and siz[mxson[r]]>=(sz+1)/2)
		{
			r=mxson[r];
		}
//		cerr<<"G="<<r<<endl;
		bel[r]=0;
		dfs1(r,r);
		++gcnt;
		vector<pair<int,int>> sp;
		for(auto x:subs)
		{
//			cerr<<x<<' '<<bel[x]<<endl;
			good[x]=gcnt;
			dis[x]=inf;
			if(x==r)continue;
			for(auto [y,w]:G[x])
			{
				if(x<y and bel[x]!=bel[y])
					sp.emplace_back(x,y);
			}
		}
		dijk(r,gcnt);
		for(auto [a,b,c]:curq)
		{
			ans[c]=min(ans[c],dis[a]+dis[b]);
//			cerr<<"upd "<<a<<' '<<b<<' '<<dis[a]+dis[b]<<endl;
		}
		for(auto [x,y]:sp)
		{
			for(auto z:subs)
			{
				dis[z]=inf;
			}
			dijk(x,gcnt);
			for(auto [a,b,c]:curq)
			{
//				cerr<<"upd "<<a<<' '<<b<<' '<<dis[a]+dis[b]<<endl;
				ans[c]=min(ans[c],dis[a]+dis[b]);
			}
			deledge(x,y);
		}
		used[r]=1;
		for(auto v:T[r])
		{
			if(not used[v])
			{
				vector<tuple<int,int,int>> tmpq;
				for(auto [a,b,c]:curq)
				{
					if(bel[a]==v and bel[b]==v)
						tmpq.emplace_back(a,b,c);
				}
				Divide(v,tmpq);
			}
		}
	};
	Divide(1,qu);
	
	for(int i=1;i<=q;i++)
		cout<<ans[i]<<"\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3840kb

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: 3624kb

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: 3608kb

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: 0
Accepted
time: 229ms
memory: 46148kb

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:

ok 250000 numbers

Test #5:

score: -100
Wrong Answer
time: 127ms
memory: 46296kb

input:

99998
1 479670338308
2 121499701200
3 858712975908
4 144714509693
5 285977224040
6 864876191776
7 68574926716
8 310308615852
9 502806496434
10 361482163495
11 765497528076
12 895859015474
13 334706003457
14 379981526252
15 36757813515
16 157157422672
17 349512227463
18 338990361716
19 163391039440
2...

output:

479670338308
1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000000
1000000000000000000
1000000...

result:

wrong answer 2nd numbers differ - expected: '601170039508', found: '1000000000000000000'