QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#86696#5034. >.<XZTmaxsmall6750 276ms186852kbC++232.7kb2023-03-10 16:28:572023-03-10 16:28:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-10 16:28:58]
  • 评测
  • 测评结果:50
  • 用时:276ms
  • 内存:186852kb
  • [2023-03-10 16:28:57]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long 
using namespace std;
const int N=4e5+100;
int n,m,k;
ll dis[N];
int vis[N],tag[N]; 
vector<pii>g[N]; 
map<int,int>val[N];
priority_queue<pair<int,ll>,vector<pair<int,ll> >,greater<pair<int,ll> > >q;
namespace Seg
{
	#define midd ((L+R)>>1) 
	int tot;
	int rt[N],ls[N<<5],rs[N<<5];
	pii val[N<<5];
	void cpy(int x,int y){ls[x]=ls[y];rs[x]=rs[y];}
	int New(){return ++tot;}
	void insert(int &x,int y,int p,int L,int R,pii v)
	{
		cpy(x=++tot,y);
		if(L==R)return val[x]=v,void();
		const int mid=midd;
		if(p<=mid)insert(ls[x],ls[y],p,L,mid,v);
		else insert(rs[x],rs[y],p,mid+1,R,v);
	}
	int query(int x,int p,int L,int R)
	{
		if(!x)return 0;
		if(L==R)return val[x].fi;
		const int mid=midd;
		if(p<=mid)return query(ls[x],p,L,mid);
		return query(rs[x],p,mid+1,R);
	}
	void add(int &x,int L,int R,int v)
	{
		if(!x)return;
		if(L==R)
		{
			int y,z;tie(y,z)=val[x];
			if(!tag[y]&&dis[y]>v+z)dis[y]=v+z,q.push(mp(dis[y],y));
			return x=0,void();
		}
		const int mid=midd;
		add(ls[x],L,mid,v);add(rs[x],mid+1,R,v);
		x=0; 
	}
}
namespace Trie
{
	int rt,tot;
	int id[N],fail[N];
	map<int,int>ch[N];
	void build()
	{
		queue<int>q;
		for(int x=1;x<=n;x++)
		{
			q.push(x);
			for(auto y:g[x])Seg::insert(Seg::rt[x],Seg::rt[x],y.fi,1,n,y);
		}
		while(!q.empty())
		{
			int x=q.front();q.pop();
			if(fail[x])tag[x]|=tag[fail[x]],Seg::cpy(Seg::rt[x]=++Seg::tot,Seg::rt[fail[x]]);
			for(auto t:ch[x])
			{
				int y,num;tie(y,num)=t;
				Seg::insert(Seg::rt[x],Seg::rt[x],y,1,n,mp(num,val[id[x]][y]));
				if(ch[fail[x]].find(y)!=ch[fail[x]].end())fail[num]=ch[fail[x]][y];
				else fail[num]=Seg::query(Seg::rt[fail[x]],y,1,n);
				q.push(num);
			}
		}
	}
}
signed main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1,x,y,z;i<=m;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		g[x].push_back(mp(y,z)),val[x][y]=z;
	}
	for(int i=1;i<=n;i++)Trie::ch[Trie::rt][i]=++Trie::tot,Trie::id[Trie::tot]=i;
	for(int i=1;i<=k;i++)
	{
		int p,x=Trie::rt;scanf("%lld",&p);
		for(int j=1,y;j<=p;j++)
		{
			scanf("%lld",&y);
			if(Trie::ch[x].find(y)==Trie::ch[x].end())Trie::ch[x][y]=++Trie::tot,Trie::id[Trie::tot]=y;
			x=Trie::ch[x][y];
		}
		tag[x]=1;
	}
	Trie::build();
	for(int i=0;i<=n;i++)dis[i]=1e18;
	q.push(mp(0,1));dis[1]=0;
	while(!q.empty())
	{
		int x=q.top().se;q.pop();
		if(vis[x]||tag[x])continue;vis[x]=1;
		if(Trie::id[x]==n)return printf("%lld\n",dis[x]),0;
		Seg::add(Seg::rt[x],1,n,dis[x]);
	}
	puts("-1");
	return 0;
}

详细

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 3ms
memory: 58484kb

input:

35 100 0
34 7 447733879
24 20 187005344
14 34 654502303
2 31 865194349
20 33 9517055
33 15 991889891
24 33 395599993
13 16 237525328
9 5 373850826
30 34 391470240
10 7 650077565
26 10 400825980
34 27 189924713
19 27 907609573
20 10 614945312
10 5 960007605
1 7 984076202
32 25 539699728
24 31 2553027...

output:

1970522617

result:

ok single line: '1970522617'

Test #2:

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

input:

35 100 0
3 12 720466531
8 12 396056603
29 21 717362482
34 13 785882968
7 13 748993858
9 28 371041056
5 22 279747660
10 13 511029466
9 10 90421686
24 13 68485905
12 17 589986641
26 3 49095373
15 24 515201376
10 33 672973479
29 31 705185599
27 22 689337965
20 4 145960570
31 28 136121037
28 5 202143094...

output:

2296067497

result:

ok single line: '2296067497'

Test #3:

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

input:

35 100 0
22 20 355360466
23 35 601550723
3 27 186544474
6 24 134507727
25 2 672165808
19 1 711018563
32 16 669385420
27 11 750652665
14 11 158441860
25 14 53347528
2 20 140122295
33 20 112964489
14 6 253781013
18 14 771123144
17 35 508607402
3 19 403442205
30 16 336645858
24 22 470183063
31 22 10734...

output:

1517028140

result:

ok single line: '1517028140'

Test #4:

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

input:

35 100 0
32 5 808438527
26 23 888346324
14 19 992303007
23 1 278329540
17 29 587913784
4 33 770924125
2 5 605204525
1 21 657667587
9 35 444108546
22 12 391857443
31 33 184589665
7 14 826884170
10 32 241928783
3 17 634515992
9 34 429624654
1 18 736971857
6 9 625772037
20 18 344038507
12 25 24408330
4...

output:

1502429426

result:

ok single line: '1502429426'

Test #5:

score: 0
Accepted
time: 10ms
memory: 57668kb

input:

35 100 0
1 9 150223804
13 25 225623874
27 10 826064515
7 31 111586392
27 4 627187519
8 7 517189480
10 13 427167940
24 14 563496
27 23 119441879
13 31 712972744
34 13 128158051
16 13 146964967
31 14 860155206
25 5 431208773
24 11 48709486
29 10 694088474
11 1 801122521
12 10 369399315
21 29 399505482...

output:

1355451140

result:

ok single line: '1355451140'

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #6:

score: 0
Wrong Answer
time: 19ms
memory: 58268kb

input:

35 100 10
11 2 380526516
9 1 213280408
20 1 775174358
23 33 14349082
32 11 781584201
10 26 572662203
8 12 157664649
23 20 327195474
15 25 861545590
6 18 838910534
21 27 91640650
19 26 995166014
4 2 878565098
4 34 523383573
26 18 578962566
31 6 874478934
11 8 398592349
10 7 643306798
13 28 290421417
...

output:

3952106015

result:

wrong answer 1st lines differ - expected: '1980354133', found: '3952106015'

Subtask #3:

score: 30
Accepted

Test #11:

score: 30
Accepted
time: 263ms
memory: 182588kb

input:

50000 200000 1
7542 37166 116613326
3581 43961 629220971
12873 42953 440313807
31744 5286 697832848
25882 12748 106667302
34760 29676 181570340
41570 9240 885513989
22227 35688 63657981
43180 29194 174058940
8977 41899 48262624
7465 18291 600002514
46925 9281 951474878
2115 31162 373758881
5386 3798...

output:

2526392504

result:

ok single line: '2526392504'

Test #12:

score: 0
Accepted
time: 276ms
memory: 184224kb

input:

50000 200000 1
24782 12463 176168576
48875 16935 741763277
36966 21304 496529510
23163 41091 139899126
22017 12255 642957842
20239 21407 267962408
9992 39550 648664588
46678 18079 745576109
21525 40647 668173200
15499 45167 948835398
236 25231 504169193
1144 26236 160922096
5068 22529 596773743
2293...

output:

2916905009

result:

ok single line: '2916905009'

Test #13:

score: 0
Accepted
time: 227ms
memory: 186852kb

input:

50000 200000 1
44987 47473 603921908
19076 14543 979792861
40477 5097 975772708
10156 43592 986014532
38276 14331 883008937
27568 17017 379894398
20669 13688 619117263
10452 28268 302961670
49932 14669 219573245
21299 37089 111817304
166 9139 579564241
39624 47105 454768157
36321 44135 475008487
154...

output:

2437330315

result:

ok single line: '2437330315'

Test #14:

score: 0
Accepted
time: 275ms
memory: 182440kb

input:

50000 200000 1
23044 25813 938979371
13825 12053 600535744
40300 48533 976220497
27950 9733 185539918
17753 40163 441723428
16971 12159 195868379
46052 16991 663733811
7358 22733 618903475
2686 14738 147547542
35603 33025 563640588
27600 13132 146407801
4349 35144 646562628
34069 5239 661848564
2670...

output:

2525861695

result:

ok single line: '2525861695'

Test #15:

score: 0
Accepted
time: 199ms
memory: 183368kb

input:

50000 200000 1
7010 49706 41082166
103 46014 91170674
28554 6661 235249419
24817 37664 390481853
21256 38170 713774964
5638 33537 671772217
18117 23810 806403210
4928 24506 263165151
19583 15308 101634127
1571 48099 527342772
46438 27069 966211201
12628 13976 545976032
48175 1310 804025336
22339 471...

output:

2343184542

result:

ok single line: '2343184542'

Subtask #4:

score: 0
Skipped

Dependency #2:

0%