QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#105990#6101. Ring Road1kriRE 5ms18680kbC++144.6kb2023-05-16 10:12:302023-05-16 10:12:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-16 10:12:32]
  • 评测
  • 测评结果:RE
  • 用时:5ms
  • 内存:18680kb
  • [2023-05-16 10:12:30]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define ll long long
using namespace std;
const ll inf=1000000000000000000ll;
void updmin(ll &x,ll y){
	if (y<x)x=y;
	return;
}
int _abs(int x){
	if (x<0)return -x;
	return x;
}
int n,q;
vector<int> e[200005];
vector<ll> ew[200005];
int m,u[400005],v[400005],first[200005],nxt[400005];
ll w[400005];
void add_edge(int a,int b,ll c){
	int i=++m;
	u[i]=a,v[i]=b,w[i]=c;
	nxt[i]=first[u[i]],first[u[i]]=i;
	i=++m;
	u[i]=b,v[i]=a,w[i]=c;
	nxt[i]=first[u[i]],first[u[i]]=i;
	return;
}
int tot,c[200005];
void build(int now){
	if (e[now].size()==0)c[++tot]=now;
	else{
		int t=now;
		for (int i=0;i<(int)e[now].size();i++){
			++n;
			add_edge(t,n,0);
			add_edge(n,e[now][i],ew[now][i]);
			t=n;
		}
		for (int i=0;i<(int)e[now].size();i++)build(e[now][i]);
	}
	return;
}
int a[300005],b[300005];
vector<int> qid[200005];
ll ans[300005];
struct Edge{
	int u,v;
	ll w;
};
Edge make_Edge(int u,int v,ll w){
	Edge ans;
	ans.u=u,ans.v=v,ans.w=w;
	return ans;
}
namespace Graph{
	vector<int> id;
	vector<Edge> e;
	int m,u[400005],v[400005],first[200005],nxt[400005];
	ll w[400005];
	void add_edge(int a,int b,ll c){
		int i=++m;
		u[i]=a,v[i]=b,w[i]=c;
		nxt[i]=first[u[i]],first[u[i]]=i;
		i=++m;
		u[i]=b,v[i]=a,w[i]=c;
		nxt[i]=first[u[i]],first[u[i]]=i;
		return;
	}
	struct node{
		int id;
		ll dis;
		bool operator <(const node &y)const{
			return y.dis<dis;
		}
	};
	node make_node(int id,ll dis){
		node ans;
		ans.id=id,ans.dis=dis;
		return ans;
	}
	priority_queue<node> h;
	int book[200005];
	ll dis[200005];
	void build(vector<int> _id,vector<Edge> _e){
		id=_id,e=_e;
		for (int i=0;i<(int)e.size();i++)add_edge(e[i].u,e[i].v,e[i].w);
		return;
	}
	void upd(Edge x){
		for (int i=0;i<(int)id.size();i++)book[id[i]]=0,dis[id[i]]=inf;
		dis[x.u]=dis[x.v]=0;
		h.push(make_node(x.u,0));
		h.push(make_node(x.v,0));
		while(!h.empty()){
			int now=(h.top()).id;
			h.pop();
			if (book[now]==1)continue;
			book[now]=1;
			for (int i=first[now];i;i=nxt[i])
				if (dis[v[i]]>dis[now]+w[i]){
					dis[v[i]]=dis[now]+w[i];
					h.push(make_node(v[i],dis[v[i]]));
				}
		}
		for (int i=0;i<(int)id.size();i++)book[id[i]]=1;
		for (int i=0;i<(int)id.size();i++)
			for (int j=0;j<(int)qid[id[i]].size();j++){
				int t=qid[id[i]][j];
				if (book[a[t]]==1&&book[b[t]]==1)updmin(ans[t],dis[a[t]]+x.w+dis[b[t]]);
			}
		return;
	}
	void clear(){
		while(m>0){
			nxt[m]=first[u[m]]=0;
			u[m]=v[m]=w[m]=0;
			m--;
		}
		for (int i=0;i<(int)id.size();i++)book[id[i]]=0;
		id.clear();
		e.clear();
		return;
	}
}
int book[200005];
int sum_n,fa[200005],sz[200005],rt;
void find_rt(int now,int f){
	fa[now]=f;
	sz[now]=1;
	for (int i=first[now];i;i=nxt[i])
		if (v[i]!=f&&book[v[i]]==1){
			find_rt(v[i],now);
			sz[now]+=sz[v[i]];
		}
	if (rt==0||_abs(2*sz[now]-sum_n)<=_abs(2*sz[rt]-sum_n))rt=now;
	return;
}
int col[200005];
void get_col(int now,int f){
	col[now]=1;
	for (int i=first[now];i;i=nxt[i])
		if (v[i]!=f&&book[v[i]]==1)get_col(v[i],now);
	return;
}
void work(vector<int> id,vector<Edge> e){
	if ((int)id.size()==1)return;
	for (int i=0;i<(int)id.size();i++)book[id[i]]=1;
	sum_n=(int)id.size(),rt=0;
	find_rt(id[0],0);
	int x=rt,y=fa[rt];
	get_col(x,y);
	vector<Edge> _e=e;
	for (int i=0;i<(int)id.size();i++)
		for (int j=first[id[i]];j;j=nxt[j])
			if (book[v[j]]==1&&v[j]!=fa[u[j]])_e.push_back(make_Edge(u[j],v[j],w[j]));
	Graph::build(id,_e);
	vector<int> id_x,id_y;
	vector<Edge> e_x,e_y;
	for (int i=0;i<(int)id.size();i++)
		if (col[id[i]]==1)id_x.push_back(id[i]);
		else id_y.push_back(id[i]);
	for (int i=0;i<(int)e.size();i++)
		if (col[e[i].u]==1&&col[e[i].v]==1)e_x.push_back(e[i]);
		else if (col[e[i].u]==0&&col[e[i].v]==0)e_y.push_back(e[i]);
		else Graph::upd(e[i]);
	for (int i=first[x];i;i=nxt[i])
		if (v[i]==y)Graph::upd(make_Edge(u[i],v[i],w[i]));
	for (int i=0;i<(int)id.size();i++)book[id[i]]=col[id[i]]=0;
	Graph::clear();
	work(id_x,e_x);
	work(id_y,e_y);
	return;
}
int main(){
	cin>>n;
	for (int i=2;i<=n;i++){
		int p;
		ll c;
		scanf("%d%lld",&p,&c);
		e[p].push_back(i);
		ew[p].push_back(c);
	}
	build(1);
	vector<int> id;
	vector<Edge> qwq;
	for (int i=1;i<=n;i++)id.push_back(i);
	for (int i=1;i<=tot;i++){
		ll x;
		scanf("%lld",&x);
		qwq.push_back(make_Edge(c[i],c[i%tot+1],x));
	}
	cin>>q;
	for (int i=1;i<=q;i++){
		scanf("%d%d",&a[i],&b[i]);
		qid[a[i]].push_back(i);
		qid[b[i]].push_back(i);
		ans[i]=inf;
	}
if (n>11451)q=0;
	work(id,qwq);
	for (int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}

详细

Test #1:

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

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: 5ms
memory: 18680kb

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: 1ms
memory: 18500kb

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
Runtime Error

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: