QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#300831#6101. Ring RoadPhantomThresholdWA 4125ms40044kbC++204.0kb2024-01-08 21:25:042024-01-08 21:25:05

Judging History

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

  • [2024-01-08 21:25:05]
  • 评测
  • 测评结果:WA
  • 用时:4125ms
  • 内存:40044kb
  • [2024-01-08 21:25:04]
  • 提交

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);
		addedge(lf[(i+1)%lcnt],lf[i],c,0);
	}
	int q;
	cin>>q;
	vector<ll> ans(q+5,inf);
	vector<tuple<int,int,int>> qu(q+5);
	for(int i=1;i<=q;i++)
	{
		int u,v;
		cin>>u>>v;
		qu[i]=make_tuple(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];
		while(mxson[r] and siz[mxson[r]]>=sz/2)
		{
			r=mxson[r];
		}
//		cerr<<"G="<<r<<endl;
		
		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]);
		}
		for(auto [x,y]:sp)
		{
			for(auto z:subs)
			{
				dis[z]=inf;
			}
			dijk(x,gcnt);
			for(auto [a,b,c]:curq)
			{
				ans[c]=min(ans[c],dis[a]+dis[b]);
			}
			deledge(x,y);
		}
		used[u]=1;
		for(auto v:T[u])
		{
			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;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3580kb

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

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

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: 4125ms
memory: 40044kb

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
1702996
1901358
1930183
2555577
2869777
3140430
3202059
3853056
4546095
4705672
5172380
5888168
6150939
6766241
6767698
7418079
7960731
8062724
8260661
8735113
9594744
9922270
10627792
11128502
11723552
12300816
13256074
13526041
13530053
14001488
14753301
15114462
16005534
16017534
16926639
...

result:

wrong answer 2nd numbers differ - expected: '335116', found: '1702996'