QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#86690#5034. >.<XZTmaxsmall670 194ms100312kbC++232.6kb2023-03-10 16:20:422023-03-10 16:20:45

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:20:45]
  • 评测
  • 测评结果:0
  • 用时:194ms
  • 内存:100312kb
  • [2023-03-10 16:20:42]
  • 提交

answer

#include<bits/stdc++.h>
#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=2e5+100;
int n,m,k;
ll dis[N];
int vis[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(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],tag[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);
			}
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1,x,y,z;i<=m;i++)
	{
		scanf("%d%d%d",&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("%d",&p);
		for(int j=1,y;j<=p;j++)
		{
			scanf("%d",&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];
		}
		Trie::tag[x]=1;
	}
	Trie::build();
	memset(dis,0x3f,sizeof(dis));
	q.push(mp(0,1));dis[1]=0;
	while(!q.empty())
	{
		int x=q.top().se;q.pop();
		if(vis[x]||Trie::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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 32252kb

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:

319841322

result:

wrong answer 1st lines differ - expected: '1970522617', found: '319841322'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 194ms
memory: 100312kb

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:

-93836876

result:

wrong answer 1st lines differ - expected: '2526392504', found: '-93836876'

Subtask #4:

score: 0
Skipped

Dependency #2:

0%