QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#717582#9352. Highway BusesXinyoucuo1dui#ML 7ms161664kbC++235.4kb2024-11-06 18:23:462024-11-06 18:23:47

Judging History

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

  • [2024-12-10 15:19:00]
  • hack成功,自动添加数据
  • (/hack/1277)
  • [2024-11-06 18:23:47]
  • 评测
  • 测评结果:ML
  • 用时:7ms
  • 内存:161664kb
  • [2024-11-06 18:23:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,an[1000001],de[1000001],cnt,fa[1000001],vi[1000001],g[1000001],vv[1000001],st[1000001],cn,q,w,h[30000001];
struct p{long long q,w;bool operator < (const p &aa) const{return w>aa.w;};}l[1000001];
vector<p> qu[1000001],qu1[1000001],qu2[1000001];
queue<int> quu;
int find(int qq){return qq==fa[qq]?qq:fa[qq]=find(fa[qq]);}
void merge(int qq,int ww)
{
	int f1=find(qq),f2=find(ww);
	if(f1==f2) return;fa[f1]=f2;
}
void dfs(int qq,int ww)
{
	vv[qq]=1;
	for(int i=0;i<qu1[qq].size();i++)
	{
		if(vv[qu1[qq][i].q]) continue;
		vi[qu1[qq][i].w]=1;
		dfs(qu1[qq][i].q,qq);
	}
}
vector<int> tmp;
void dfs1(int qq)
{
	vi[qq]=1;tmp.push_back(qq);
	for(int i=0;i<qu1[qq].size();i++)
	{
		if(vi[qu1[qq][i].q]) continue;
		dfs1(qu1[qq][i].q);
	}
}
long long di[103][200001],si[200001],v[200001],all,mx=1e9,rt,mxd;
void dfs2(int qq,int ww)
{
	long long mxx=0;
	for(int i=0;i<qu2[qq].size();i++)
	{
		if(qu2[qq][i].q==ww) continue;
		if(v[qu2[qq][i].q]) continue;
		dfs2(qu2[qq][i].q,qq);
		si[qq]+=si[qu2[qq][i].q];
		mxx=max(mxx,si[qu2[qq][i].q]);
	}
	mxx=max(mxx,all-si[qq]);
	if(mxx<mx) mx=mxx,rt=qq;
}
vector<int> ve[1000001];
void dfs3(int qq,int ww)
{
	de[qq]=de[ww]+1;mxd=max(mxd,de[qq]);
	ve[de[qq]].push_back(qq);
	for(int i=0;i<qu2[qq].size();i++)
	{
		if(qu2[qq][i].q==ww||v[qu2[qq][i].q]) continue;
		dfs3(qu2[qq][i].q,qq);
	}
}
int h1[30000001],o;
struct pp{int q,w;}l1[35000001];
vector<int> id[1000001];
long long t[1000001],ls[1000001];
void add(int qq,int ww)
{
	l1[++o].q=ww,l1[o].w=h1[qq],h1[qq]=o;
}
void link(int qq,int ww,long long ee)
{
	if(ee<0) return;
	++ee;
	ee=min(ee,t[ww]);
	add(qq,id[ww][ee]);
}
void work(int qq)
{
	mxd=0;
	dfs3(qq,0);
	id[qq].resize(mxd+2);
	int lss=0;t[qq]=mxd;
	for(int i=1;i<=mxd;i++)
	{
		++cnt;
		id[qq][i]=cnt;
		if(lss) add(cnt,lss);
		for(int j=0;j<ve[i].size();j++) add(cnt,ve[i][j]);
		lss=cnt;
	}
	for(int i=1;i<=mxd;i++)
	{
		for(int j=0;j<ve[i].size();j++)
		{
//			cout<<ve[i][j]<<" "<<qq<<" "<<l[ve[i][j]].q-(i-1)<<"\n";
			link(ve[i][j],qq,l[ve[i][j]].q-(i-1));
		}
	}
	for(int i=1;i<=mxd;i++) ve[i].clear();
}
void solve(int qq)
{
	work(qq);v[qq]=1;
	for(int i=0;i<qu2[qq].size();i++)
	{
		int tt=qu2[qq][i].q;
		if(v[tt]) continue;
		all=si[tt],mx=1e9,rt=0;
		dfs2(tt,qq);
		fa[rt]=qq;
		solve(rt);
	}
}
void work(vector<int> qq)
{
//	for(int i=0;i<qq.size();i++) cout<<qq[i]<<" ";cout<<"\n";
	for(int i=0;i<qq.size();i++) vv[qq[i]]=1;
	all=0;
	for(int i=0;i<qq.size();i++)
	{
		int tt=qq[i];v[tt]=0;all++;
		fa[tt]=0;
		qu2[tt].clear();
		for(int j=0;j<qu1[tt].size();j++)
		{
			if(vv[qu1[tt][j].q]) qu2[tt].push_back(qu1[tt][j]);
		}
	}
	mx=1e9;
	dfs2(tmp[0],0);
	solve(rt);
	for(int i=0;i<qq.size();i++) vv[qq[i]]=0;
}
priority_queue<p> Qu;
void work()
{
	while(!Qu.empty()) Qu.pop();
	Qu.push(p{1,l[1].w});
	for(int i=1;i<=cnt;i++) h[i]=-1;
	h[1]=l[1].w;
	while(!Qu.empty())
	{
		int r=Qu.top().q;Qu.pop();
//		cout<<r<<" ";
		for(int i=h1[r];i;i=l1[i].w)
		{
			int tt=l1[i].q;
			if(h[tt]==-1)
			{
				if(tt>a) h[tt]=h[r];
				else h[tt]=h[r]+l[tt].w;
				Qu.push(p{tt,h[tt]});
			}
		}
	}
	for(int i=1;i<=a;i++) an[i]=min(an[i],h[i]-l[i].w);
}
long long mxxd;
void dfs4(int qq,int ww)
{
	de[qq]=de[ww]+1;ve[de[qq]-1].push_back(qq);//mxdd=max(mxdd,de[qq]-1);
	for(int i=0;i<qu1[qq].size();i++)
	{
		if(qu1[qq][i].q==ww||vi[qu1[qq][i].q]) continue;
		dfs4(qu1[qq][i].q,qq);
	}
}
int main()
{
	scanf("%lld%lld%lld",&a,&b,&c);
	for(int i=1;i<=a;i++)
	{
		scanf("%lld%lld%lld",&l[i].q,&l[i].w,&g[i]);
	}
	for(int i=1;i<=b;i++)
	{
		scanf("%lld%lld",&q,&w);
		qu[q].push_back(p{w,i});
		qu[w].push_back(p{q,i});
	}
	cnt=a+b;
	for(int i=1;i<=cnt;i++) vi[i]=0,vv[i]=0;
	cnt=a;
	for(int i=1;i<=a;i++) qu1[i]=qu[i];
	for(int i=1;i<=a;i++) de[i]=0;
	dfs(1,0);cn=0;
	for(int i=1;i<=a;i++)
	{
		for(int j=0;j<qu1[i].size();j++)
		{
			if(!vi[qu1[i][j].w])
			{
				st[++cn]=i;
			}
		}
	}
	sort(st+1,st+cn+1);cn=unique(st+1,st+cn+1)-st-1;
//	for(int i=1;i<=cn;i++) cout<<st[i]<<" ";cout<<"\n";
	for(int i=1;i<=a;i++) vi[i]=0,vv[i]=0;
	for(int i=1;i<=cn;i++) vi[st[i]]=1;
	for(int i=1;i<=cn;i++)
	{
		for(int j=1;j<=a;j++) di[i][j]=-1;
		di[i][st[i]]=0;
		while(!quu.empty()) quu.pop();
		quu.push(st[i]);
		while(!quu.empty())
		{
			int r=quu.front();quu.pop();
			for(int j=0;j<qu1[r].size();j++)
			{
				if(di[i][qu1[r][j].q]==-1)
				{
					di[i][qu1[r][j].q]=di[i][r]+1;
					quu.push(qu1[r][j].q);
				}
			}
		}
	}
	for(int i=1;i<=a;i++) an[i]=1e18;
	for(int i=1;i<=a;i++)
	{
		if(!vi[i])
		{
			tmp.clear();
			dfs1(i);
			work(tmp);
		}
	}
	for(int i=1;i<=a;i++) vi[i]=0;
	for(int i=1;i<=cn;i++) vi[st[i]]=1;
	for(int i=1;i<=cn;i++)
	{
		for(int j=0;j<=a;j++) ve[j].clear();
		dfs4(st[i],0);
		for(int j=1;j<=cn;j++)
		{
			if(i==j) continue;
			ve[di[i][st[j]]].push_back(st[j]);
		}
		long long mxx=0;
		for(int j=0;j<=a;j++)
		{
			if(!ve[j].size()) break;
			mxx=j;
			++cnt;ls[j]=cnt;
			if(j>0) add(ls[j],ls[j-1]);
			for(int k=0;k<ve[j].size();k++)
			{
				add(ls[j],ve[j][k]);
			}
		}
		for(int j=1;j<=a;j++)
		{
			long long nww=l[j].q-di[i][j];
			nww=min(nww,mxx);
			if(nww>=0)
			{
				add(j,ls[nww]);
			}
		}
	}
	work();
	for(int i=1;i<=a;i++)
	{
		l[i].w+=g[i]*(c-1);
	}
	work();
	for(int i=1;i<=a;i++) printf("%lld\n",an[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 34536kb

input:

6 6 2
1 50 -40
1 2 100
2 1 100
2 4 100
3 1 100
1 1 100
1 2
2 3
3 4
4 2
2 5
6 1

output:

0
10
52
52
52
10

result:

ok 6 lines

Test #2:

score: 0
Accepted
time: 4ms
memory: 139224kb

input:

500 540 1000000
1 831790353 70
3 624594642 -127
2 189318946 -92
1 858646508 320
4 76999645 671
4 780012318 880
2 51254764 -12
2 420182468 -333
3 314764053 -36
1 560114854 -419
2 484412868 -31
3 466851594 6
4 535326027 732
4 430602789 578
1 605236859 43
4 633715178 896
3 110060408 -9
4 878946915 -654...

output:

0
1277292628
1239671692
1255261807
1284074004
1270230633
1239671692
1284074004
1271369537
1277292628
1205507860
1270615693
1300179417
1205507860
1205507860
1239671692
1251564675
1239671692
1284004371
1239671692
1239671692
1277292628
1270230633
1284004371
1277292628
1255261807
1276194392
1247939403
1...

result:

ok 500 lines

Test #3:

score: 0
Accepted
time: 7ms
memory: 141272kb

input:

500 540 1000000
1 613142394 -268
5 920609625 740
2 755612530 -255
2 23678897 -4
5 325892468 291
5 707223319 -140
1 679600699 -138
5 625157055 690
2 141819870 995
1 250348582 -219
2 581461324 -580
4 339782234 -82
5 810851082 230
3 378119535 158
4 295102386 677
5 854435300 21
3 565535907 -465
2 820995...

output:

0
2421015760
2617367920
2694215005
2812156460
2412108889
2370843291
2786283443
2412108889
2197157944
2412108889
2633707306
2370843291
2478757415
2672183755
2478757415
2633707306
2812156460
1984181483
2464420418
2548091380
2421015760
2421015760
2412108889
2421015760
2421015760
2412108889
2412108889
2...

result:

ok 500 lines

Test #4:

score: 0
Accepted
time: 4ms
memory: 145272kb

input:

500 544 1000000
2 587500219 -573
3 800375803 -606
2 332196789 -11
2 782258272 270
2 690828422 -145
2 642751384 -107
4 78645508 -68
3 692764955 364
5 739361677 -104
4 139030619 -125
5 698401632 -121
3 654935300 401
4 70734757 -57
2 763502749 911
1 71485824 836
1 292976518 -290
1 743618801 659
2 64895...

output:

0
425794735
442014967
675968705
311908134
675968705
336563578
425794735
523701048
479984544
425794735
425794735
425794735
708001283
311908134
1653971237
425794735
580659172
425794735
487630114
311908134
450399440
1653971237
425957613
425794735
425957613
336604992
336604992
425794735
436034689
425794...

result:

ok 500 lines

Test #5:

score: 0
Accepted
time: 7ms
memory: 145384kb

input:

500 543 1000000
4 753661240 -312
2 281450837 -151
9 28464686 987
7 685967710 490
8 592650944 542
10 141100249 83
10 646501804 -94
3 337312645 294
2 904175548 -870
8 281667853 -136
3 36477141 -26
5 476645115 -195
1 21897824 -7
10 517151723 150
1 291410319 941
7 993616997 143
10 628559241 -428
8 10757...

output:

0
445387723
445387723
450719457
455897864
445387723
449974501
449974501
449974501
444157947
449974501
449974501
449974501
449974501
449974501
445387723
441661552
449974501
449974501
449974501
444157947
444157947
444157947
449974501
444157947
444157947
449974501
445387723
441661552
449974501
45156161...

result:

ok 500 lines

Test #6:

score: 0
Accepted
time: 7ms
memory: 141216kb

input:

500 547 1000000
7 579418 0
1 769742 0
1 133755 0
2 996071 0
2 96075 893
7 484503 0
7 645976 141
6 80570 0
2 33751 124
4 218617 701
5 686104 0
1 675119 586
3 294461 0
5 319865 0
9 178301 179
1 547068 0
1 96921 802
3 725739 58
8 646648 0
4 667865 0
6 816462 0
4 901406 37
4 834211 0
1 364051 263
2 1014...

output:

0
653962
626600
579418
626600
603269
603269
626600
626600
634782
626600
672297
579418
626600
626600
579418
626600
579418
626600
672297
626600
661975
672297
746441
626600
661975
626600
626600
626600
626600
579418
626600
653962
661975
626600
626600
579418
579418
626600
579418
579418
626600
634782
6266...

result:

ok 500 lines

Test #7:

score: 0
Accepted
time: 7ms
memory: 161664kb

input:

500 549 1000000
8 275979 799
2 323404 0
8 286448 610
2 877230 292
5 111405 972
2 686865 757
6 542128 0
9 823472 705
8 551203 0
9 900802 0
8 497319 554
2 60284 473
1 128784 147
1 390099 282
1 376548 407
7 444338 502
10 496911 293
7 133528 0
1 949531 669
8 569605 459
1 310534 504
2 705803 0
5 954861 0...

output:

0
308634
296602
275979
275979
275979
308634
296754
296602
275979
296602
308634
275979
275979
275979
296602
275979
296602
275979
296602
308634
296602
275979
300889
275979
275979
275979
275979
296754
296602
324141
275979
296754
296754
308634
296602
308634
308634
275979
296754
275979
275979
324141
2759...

result:

ok 500 lines

Test #8:

score: -100
Memory Limit Exceeded

input:

30000 30047 786577
2 418118 886
1 923620 -1
1 396304 59
1 357673 0
1 12272 51
2 797480 0
2 41479 797
1 970539 -1
1 608143 0
2 415150 0
1 459616 0
1 739232 742
1 917012 -1
1 165211 0
1 637917 550
1 238131 0
2 232835 258
2 610877 0
1 17235 0
2 112947 446
2 828314 0
2 179873 782
2 333590 0
1 961918 194...

output:

0
80494179
83741087
62038907
76473105
104910654
116145079
108446496
88716481
94285072
115284209
99860695
77584533
119165550
81758989
77570762
142596283
79902868
77267149
95599129
114945135
73806480
108069554
77051483
76742645
57016312
152581721
89223155
76282889
122548472
23429774
107080496
76205230...

result: