QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#345115#2865. 天才黑客Lynkcat0 178ms27256kbC++204.0kb2024-03-06 09:01:152024-03-06 09:01:15

Judging History

This is the latest submission verdict.

  • [2024-03-06 09:01:15]
  • Judged
  • Verdict: 0
  • Time: 178ms
  • Memory: 27256kb
Show
  • [2024-03-06 09:01:15]
  • Submitted

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
// #define N 
using namespace std;
const int N=200005;
struct node
{
	int x,y,w,d;
}E[N];
namespace tr
{
	int dfn[N],DFN;
	int ffa[N],siz[N],dep[N];
	int son[N];
	poly G[N];
	int Tp[N];
	void dfs(int k,int fa)
	{
		// cout<<"tr "<<k<<" "<<endl;
		dfn[k]=++DFN;
		ffa[k]=fa;
		siz[k]=1;
		son[k]=0;
		dep[k]=dep[fa]+1;
		for (auto u:G[k])
		{
			dfs(u,k);
			siz[k]+=siz[u];
			if (siz[u]>siz[son[k]]) son[k]=u;
		}
	}
	void dfs1(int k,int tp)
	{
		Tp[k]=tp;
		if (son[k]) dfs1(son[k],tp);
		for (auto u:G[k])
		{
			if (u==son[k]) continue;
			dfs1(u,u);
		}
	}
	inline int lca(int x,int y)
	{
		while (Tp[x]!=Tp[y])
		{
			if (dep[Tp[x]]<dep[Tp[y]]) swap(x,y);
			x=ffa[Tp[x]];
		}
		if (dep[x]<dep[y]) return x;
		return y;
	}
}
vector<pa>G[N];
poly rG[N],Q[N];
int id[N][3];
int dis[N],ans[N];
int tot;
int n,m,q;
inline void add(int x,int y,int w)
{
	G[x].push_back(mp(y,w));
	// cout<<"add "<<x<<" "<<y<<" "<<w<<endl;
}
void dfs(int k,int fa)
{
	// cout<<"??aaa "<<k<<" "<<tr::dep[k]<<endl;
	int x=0;
	for (auto u:rG[k])
	{
		dfs(u,k);
		add(id[u][0],id[k][0],0);
		add(id[k][1],id[u][1],0);
	}
	for (auto u:rG[k])
	{
		if (x) add(id[u][0],x,tr::dep[k]-1);
		++tot;
		if (x) add(tot,x,0);
		add(tot,id[u][1],0);
		x=tot;
	}
	reverse(rG[k].begin(),rG[k].end());
	x=0;
	for (auto u:rG[k])
	{
		if (x) add(id[u][0],x,tr::dep[k]-1);
		++tot;
		if (x) add(tot,x,0);
		add(tot,id[u][1],0);
		x=tot;
	}
	add(id[k][1],id[k][2],0);
	add(id[k][0],id[k][2],tr::dep[k]-1);
}
void BellaKira()
{
	cin>>n>>m>>q;
	tot=m;
	for (int i=1;i<=m;i++)
	{
		cin>>E[i].x>>E[i].y>>E[i].w>>E[i].d;
		Q[E[i].y].push_back(i);
		Q[E[i].x].push_back(i);
	}
	for (int i=1;i<q;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		tr::G[x].push_back(y);
	}
	tr::dfs(1,0);
	tr::dfs1(1,0);
	for (int i=1;i<=n;i++)
	{
		sort(Q[i].begin(),Q[i].end(),[&](int x,int y)
		{
			return tr::dfn[E[x].d]<tr::dfn[E[y].d];
		});
		poly sta,all;
		sta.push_back(1);

		all.push_back(1);
		for (auto v:Q[i])
		{
			int u=E[v].d;
			if (u==sta.back()) continue;
			if (sta.size()==1) 
			{
				sta.push_back(u);
				all.push_back(u);
				continue;
			}
			int x=tr::lca(sta.back(),u);
			while (sta.size()>=2&&tr::dfn[sta[sz(sta)-2]]>=tr::dfn[x]) rG[sta[sz(sta)-2]].push_back(sta.back()),sta.pop_back();
			if (x!=sta.back()) 
			{
				rG[x].push_back(sta.back());
				sta.pop_back();

				sta.push_back(x);
				all.push_back(x);
			}
			sta.push_back(u);
			all.push_back(u);
		}
		while (sta.size()>1) rG[sta[sz(sta)-2]].push_back(sta.back()),sta.pop_back();
		for (auto u:all) id[u][0]=++tot,id[u][1]=++tot,id[u][2]=++tot;
		dfs(1,0);
		for (auto u:all) poly().swap(rG[u]);
		for (auto u:Q[i])
			if (E[u].y==i) add(u,id[E[u].d][0],0);
			else add(id[E[u].d][2],u,E[u].w);
	}
	priority_queue<pa>q;
	for (int i=1;i<=tot;i++) dis[i]=inf;
	for (int i=1;i<=m;i++)
		if (E[i].x==1)
		{
			dis[i]=E[i].w;
			q.push(mp(-dis[i],i));
		}
	while (!q.empty())
	{
		int ww=-q.top().fi;
		int u=q.top().se;
		q.pop();
		if (ww!=dis[u]) continue;
		for (auto [v,w]:G[u])
			if (dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push(mp(-dis[v],v));
			}
	}
	for (int i=1;i<=n;i++) ans[i]=inf;
	ans[1]=0;
	for (int i=1;i<=m;i++)
		ans[E[i].y]=min(ans[E[i].y],dis[i]);
	for (int i=2;i<=n;i++) cout<<ans[i]<<'\n';

	for (int i=1;i<=tot;i++) vector<pa>().swap(G[i]);
	for (int i=1;i<=n;i++)
	{
		poly().swap(Q[i]);
	}
	for (int i=1;i<=::q;i++)
		poly().swap(tr::G[i]);
	tr::DFN=0;
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	cin>>T;
	while (T--)
	{
		BellaKira();
	}
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/
源文件, 语言: C++20

详细

Test #1:

score: 0
Wrong Answer
time: 169ms
memory: 25816kb

input:

10
6 4990 19922
4 3 6 16653
1 5 1 14907
5 3 3 12543
1 6 6 18133
6 4 0 10382
2 4 2 13389
1 6 5 11764
5 6 1 7278
1 6 3 16419
6 5 1 6237
1 4 8 9478
2 2 5 6012
6 4 7 4620
3 4 4 13781
1 3 0 4496
6 4 2 10214
6 3 2 6714
1 2 5 16272
4 3 3 16818
5 3 3 6710
6 5 9 17344
5 4 2 11112
2 3 2 2614
6 5 7 16745
4 3 9...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
2
0
0
0
1
1
0
0
0
0
0
21
5
2
0
3
2
0
0
0
0
2
1
1
2
0
2
0
1
2
0
2
2
2
0
2
5
0
2
0
3
0
0
1
0
2
0
7
3
0
6
0
4
0
2
2
7
4
16
6
8
20
12
7
1
10
7
5
3
1
1
6
7
3
6
3
0
0
9
16
7
10
3
8
9
5
7
0
8
5
7
8
1
23
10
2
1
12
5
1
8
14
4...

result:

wrong answer 192nd lines differ - expected: '384', found: '737'

Test #2:

score: 0
Wrong Answer
time: 161ms
memory: 26648kb

input:

10
6 4985 19945
3 2 2 1824
6 5 7 2420
3 4 8 16955
6 5 2 5283
3 4 0 530
4 4 5 432
1 6 1 19342
6 6 8 18901
5 4 9 19350
6 5 1 387
6 5 9 1712
6 4 4 19861
2 1 5 19663
2 2 6 19868
3 6 4 2781
4 2 1 1226
1 2 4 14349
2 5 9 10064
1 3 3 14473
3 2 3 4945
2 6 7 13433
5 4 5 12670
2 4 1 7392
4 4 9 10449
6 1 2 7280...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
6
3
1
0
0
0
0
1
7
1
4
1
7
3
0
0
2
0
0
3
2
1
1
4
0
2
0
0
4
3
0
5
15
4
15
1
1
1
2
3
0
2
2
0
0
2
3
99
5
79
6
95
11
9
12
7
16
19
3
3
62
54
1
0
0
7
4
2
5
3
1
1
2
0
11
12
7
4
5
1
29
2
3
59
3
3
2
5
1
2...

result:

wrong answer 103rd lines differ - expected: '22', found: '79'

Test #3:

score: 0
Wrong Answer
time: 178ms
memory: 26940kb

input:

10
4 4986 19949
3 3 4 10629
2 3 1 3347
4 1 1 7532
4 4 1 2251
3 3 9 14639
2 3 4 682
2 2 1 16614
1 4 4 9015
4 4 9 9520
4 3 5 14918
3 2 5 14349
1 4 9 13119
1 2 0 2659
2 2 9 19574
1 3 3 827
2 4 8 9747
2 4 9 16560
3 4 0 12866
1 4 8 826
4 2 8 8636
2 2 0 11934
4 2 5 2402
2 4 4 9539
4 1 4 17455
4 2 4 17281
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
1
0
1
0
0
2
2
0
0
2
0
0
0
0
2
0
0
1
1
0
3
39
4
3
1
1
2
1
0
5
0
3
2
5
2
0
1
7
0
3
1
0
0
0
3
0
1
4
2
2
6
0
3
0
0
0
1
0
1
0
0
2
2
0
3
2
0
2
4
17
28
2
2
6
3
2
23
24
12
42
0
8
8
6
19
23
0
16
20
17
3
3
23
7
5
19
8
2
4
0
5
16
30
9
1
20
16
4
7
1
5
...

result:

wrong answer 101st lines differ - expected: '27', found: '28'

Test #4:

score: 0
Wrong Answer
time: 156ms
memory: 26916kb

input:

10
5 4983 19992
1 3 7 4541
4 2 1 3807
2 2 5 14524
2 5 7 17852
5 5 2 1373
1 5 9 5415
2 4 5 1640
5 4 3 14802
4 4 4 13595
1 3 2 6844
5 3 8 11221
1 5 0 1494
4 5 0 12221
1 2 3 9245
5 1 9 19364
1 5 6 15902
1 5 9 15907
5 3 7 1577
4 4 6 652
2 2 2 5783
4 3 9 6039
1 2 0 12257
2 2 2 4031
1 4 1 9055
2 4 3 15081...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
4
3
4
2
1
7
0
0
0
0
0
3
3
0
1
0
0
0
6
0
1
0
4
0
7
0
0
1
5
0
3
0
2
5
2
0
1
0
0
0
3
1
2
1
3
6900
648
4
2
1
3
984
9
1454
950
1698
9
0
0
278
8
0
119
1
1
0
1
3
0
8
2
4
851
1
268
2
3
7
6
2
0
342
1227
404
0
9
40...

result:

wrong answer 94th lines differ - expected: '119', found: '6900'

Test #5:

score: 0
Wrong Answer
time: 172ms
memory: 27256kb

input:

10
4 4988 19958
3 3 6 11088
1 3 2 13262
4 1 1 13329
1 2 6 7013
2 2 4 19047
1 4 1 9111
1 1 0 13164
2 4 3 10469
1 1 5 9157
1 4 9 18420
4 3 3 6912
1 1 3 14729
4 2 5 17794
1 3 6 2306
4 4 7 9709
1 1 6 9322
1 1 2 16917
3 1 5 7401
1 1 2 12811
1 3 9 856
2 1 2 968
1 4 1 1764
1 4 1 13252
1 3 2 14558
3 4 6 989...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
2
0
2
1
1
0
0
3
0
1
1
7
1
0
3
1
0
2
1
3
0
3
0
0
2
0
1
0
18
1
2
0
0
0
0
1
0
2
1
2
4
1
5
4
4
0
4
35
1
1
3
7
0
6
8
46
1
4
2
6
1
5
20
7
2
4
1
0
2
5
8
9
19
12
4
3
0
11
9
2
11
7
8
1
5
11
1
5
11
2
6
2
5
...

result:

wrong answer 81st lines differ - expected: '14', found: '18'

Test #6:

score: 0
Runtime Error

input:

10
4 4998 19943
2 3 1 7426
1 4 9 9989
4 2 8 11254
1 2 4 10425
4 4 5 18391
1 3 7 1508
2 3 3 14690
3 2 4 15883
3 2 8 4016
2 3 2 11659
2 1 0 12607
1 4 1 10741
1 4 7 5462
3 2 1 1653
4 2 6 5168
2 3 8 14411
2 1 7 1816
1 4 4 4290
1 1 6 15831
4 2 7 8537
4 2 6 15402
3 4 2 16587
3 1 2 9686
2 3 3 9766
4 2 0 89...

output:

result:

Test #7:

score: 0
Runtime Error

input:

10
6 4984 19910
5 5 2 2264
4 4 1 541
2 5 0 19175
6 5 2 18125
1 6 2 16994
1 4 7 6497
5 4 2 10033
2 6 3 17202
4 5 9 7768
6 4 5 19834
4 3 3 16806
3 3 4 14749
2 2 7 831
2 4 2 4307
1 6 9 5587
3 5 0 9514
1 4 0 15445
1 2 1 2489
5 3 1 9696
5 3 2 4174
1 3 9 17514
2 1 4 17554
2 5 0 9930
1 6 3 6804
1 4 1 16090...

output:

result:

Test #8:

score: 0
Runtime Error

input:

10
6 4993 19952
1 3 2 6914
4 5 4 16857
3 6 2 18667
5 2 1 16058
1 2 7 2409
6 5 0 7937
4 3 6 7888
1 4 7 2644
2 2 1 19420
2 6 8 4166
1 4 2 17703
6 5 8 10459
2 2 1 8365
1 3 3 5072
3 1 4 5816
2 1 9 2924
6 6 5 4906
1 4 6 16825
1 6 0 13600
3 6 7 11572
6 6 8 12361
3 2 8 3299
2 5 1 16877
6 6 3 5290
3 4 1 816...

output:

result:

Test #9:

score: 0
Runtime Error

input:

10
6 4984 19985
1 5 9 19725
5 3 9 3224
6 4 7 17229
3 6 3 15580
4 3 3 9809
4 2 5 10336
3 4 2 2893
6 6 7 15935
1 4 8 3530
2 3 8 18657
3 5 7 2867
1 1 5 3773
1 3 5 12801
6 2 5 9859
3 6 8 6206
2 6 3 10115
5 3 2 10479
2 4 1 13091
2 1 9 4511
4 3 4 5438
3 5 7 18741
1 1 6 11781
6 4 2 9837
3 5 9 809
1 2 0 697...

output:

result:

Test #10:

score: 0
Runtime Error

input:

10
5 4981 19908
5 2 5 7847
2 4 0 17200
3 3 0 7650
5 2 2 3879
2 3 2 2556
1 2 0 5079
5 3 8 5551
4 2 0 6754
4 5 4 13987
2 3 5 19759
4 3 9 3494
2 3 1 2343
2 3 2 5505
3 2 7 6477
1 2 4 11240
2 3 7 12541
1 3 4 15664
4 3 1 8026
1 3 0 7141
5 4 6 13607
1 4 4 18417
5 4 1 13175
1 5 4 15409
2 3 6 14894
5 4 9 171...

output:

result:

Test #11:

score: 0
Runtime Error

input:

10
6 4995 19937
5 5 4 10024
4 3 2 18036
4 5 1 13191
5 4 3 258
1 1 6 1951
6 4 0 7574
2 5 1 8966
2 4 8 17232
3 5 3 16330
4 4 0 9052
3 4 8 18592
4 3 0 10853
6 5 6 260
6 2 1 7979
3 5 3 16859
5 5 7 17000
1 2 6 8282
1 6 3 957
6 4 3 9470
6 5 9 10541
2 6 8 8372
2 6 7 6297
1 2 9 15822
6 2 0 10634
1 1 7 11728...

output:

result:

Test #12:

score: 0
Runtime Error

input:

10
6 4990 19956
4 1 9 10413
6 4 7 19545
2 5 5 11491
6 5 1 3975
1 5 8 1699
3 6 0 6002
4 3 0 4921
6 6 1 15634
2 4 6 1876
1 3 0 17060
6 3 0 14890
4 2 4 17587
3 3 2 14233
3 2 2 1486
2 4 1 2002
3 2 1 6420
5 4 5 16842
4 6 6 7468
2 4 3 18938
2 2 8 3690
2 3 7 12751
5 5 1 6809
3 3 5 5196
3 2 5 8143
3 4 0 139...

output:

result:

Test #13:

score: 0
Runtime Error

input:

10
4 4992 19978
3 3 4 18114
3 2 0 9129
4 3 1 2557
1 2 4 17326
4 3 0 15118
3 3 7 14659
2 4 7 5103
2 1 5 4331
2 2 7 16062
4 4 5 16766
1 1 9 633
1 3 0 1709
2 4 8 7795
2 2 9 1723
3 2 4 9500
2 4 8 4041
1 3 6 8318
3 3 2 17002
3 1 1 13373
2 2 7 3406
4 3 9 9423
3 4 8 4516
3 1 1 5267
2 3 7 242
1 4 2 7578
2 4...

output:

result:

Test #14:

score: 0
Runtime Error

input:

10
5 4985 19935
5 5 4 3085
1 4 2 13575
5 2 5 14600
5 2 6 14953
4 1 8 18145
3 5 4 13619
2 4 8 8245
4 3 7 12415
4 4 3 2072
2 3 2 13368
2 3 8 12771
2 2 8 7915
4 4 1 3325
5 5 4 9067
1 5 8 12922
2 5 8 15516
2 3 4 7827
5 2 8 360
2 4 3 9441
5 4 6 5290
4 2 6 6563
4 4 9 14623
1 5 6 1250
1 3 8 6817
3 1 0 9708...

output:

result:

Test #15:

score: 0
Runtime Error

input:

10
6 4995 19955
3 4 3 3040
2 3 7 13043
4 3 5 8426
5 1 8 19469
1 2 2 10883
6 4 8 2424
4 3 1 1737
5 2 4 14899
1 3 1 18706
6 3 6 1681
2 3 9 17890
4 4 2 14975
6 1 9 2434
2 4 8 4355
5 4 8 3200
3 5 1 8549
1 6 2 18377
1 2 3 11612
1 2 3 5990
3 6 7 1604
6 4 8 19417
2 5 8 1461
4 3 2 17723
2 3 7 1312
5 4 6 133...

output:

result:

Test #16:

score: 0
Runtime Error

input:

10
6 4992 19968
1 6 6 16842
3 3 7 15861
5 6 0 3497
5 5 5 19954
1 2 6 2069
2 5 5 13875
2 5 5 6179
6 5 0 16086
2 4 0 18793
1 3 4 6990
5 5 1 1486
3 4 8 3505
2 2 5 2834
5 2 9 14770
2 4 7 222
3 4 6 10285
6 1 1 16750
6 6 9 5549
3 4 6 7994
4 4 8 16822
3 3 9 19233
2 3 7 315
4 1 2 3861
5 5 2 8059
4 5 7 14125...

output:

result:

Test #17:

score: 0
Runtime Error

input:

10
6 4996 19904
4 3 6 17307
1 5 4 2473
3 2 7 12144
5 3 7 6672
5 3 6 15910
3 5 6 11688
4 4 8 16190
2 1 2 15197
3 5 4 901
6 4 9 11844
3 6 1 3506
1 6 7 10385
6 3 2 2327
5 5 5 12960
5 5 9 7675
5 4 9 13836
5 2 0 5528
4 5 7 10281
2 5 2 456
1 5 1 15869
6 1 2 16706
1 6 3 14880
6 1 2 10730
4 3 5 2894
6 6 6 9...

output:

result:

Test #18:

score: 0
Runtime Error

input:

10
6 4995 19947
3 6 2 13262
2 3 1 13329
4 4 6 7013
6 4 4 19047
1 2 1 9111
5 1 0 13164
6 6 3 10469
1 2 5 9157
5 5 9 18420
1 2 3 6912
3 3 3 14729
5 2 5 17794
6 5 6 2306
6 5 7 9709
3 3 6 9322
2 6 2 16917
1 2 5 7401
3 1 2 12811
6 5 9 856
2 6 2 968
6 3 1 1764
2 4 1 13252
5 1 2 14558
4 4 6 989
3 5 0 4787
...

output:

result:

Test #19:

score: 0
Runtime Error

input:

10
4 4982 19982
1 1 1 15234
3 4 6 8936
3 1 3 13315
2 1 9 7802
1 4 3 38
1 4 3 1508
1 1 8 13255
3 3 8 12225
4 3 5 11015
3 2 8 14803
4 2 5 9461
4 3 2 2918
1 4 1 18272
2 1 6 6307
2 4 7 14377
4 2 3 16242
1 4 7 6914
4 2 8 18377
4 3 0 3930
2 1 0 11053
4 3 0 11620
2 4 8 12686
3 4 7 5323
4 3 1 11344
2 1 6 19...

output:

result:

Test #20:

score: 0
Runtime Error

input:

10
5 4995 19956
5 4 1 9042
1 3 5 15683
1 2 5 9
3 4 5 15372
3 4 4 16833
5 4 9 14900
5 5 7 8808
4 4 5 2929
2 2 2 11639
1 4 6 16942
1 2 0 18810
2 4 5 12978
1 4 7 16548
2 1 7 6791
4 4 1 14378
1 2 2 11387
3 3 1 11847
5 3 0 10333
1 4 2 15040
1 3 0 1774
5 5 2 15991
2 1 0 11377
1 4 7 13228
1 3 5 10889
1 2 0...

output:

result:
English 繁體中文 简体中文

服务器时间: 2025-02-09 01:02:15 | 开源项目