QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#86256#5034. >.<ExplodingKonjac0 180ms90292kbC++175.7kb2023-03-09 16:22:332023-03-09 16:22:34

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-09 16:22:34]
  • 评测
  • 测评结果:0
  • 用时:180ms
  • 内存:90292kb
  • [2023-03-09 16:22:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
//#define OPENIOBUF

namespace FastIO
{

class FastIOBase
{
 protected:
#ifdef OPENIOBUF
	static const int BUFSIZE=1<<22;
	char buf[BUFSIZE+1];
	int buf_p=0;
#endif
	FILE *target;
 public:
#ifdef OPENIOBUF
	virtual void flush()=0;
#endif
	FastIOBase(FILE *f): target(f){}
	~FastIOBase()=default;
};

class FastOutput: public FastIOBase
{
#ifdef OPENIOBUF
 public:
	inline void flush()
		{ fwrite(buf,1,buf_p,target),buf_p=0; }
#endif
 protected:
	inline void __putc(char x)
	{
#ifdef OPENIOBUF
		if(buf[buf_p++]=x,buf_p==BUFSIZE)flush();
#else
		putc(x,target);
#endif
	}
	template<typename T>
	inline void __write(T x)
	{
		static char stk[64],*top;top=stk;
		if(x<0) return __putc('-'),__write(-x);
		do *(top++)=x%10,x/=10; while(x);
		for(;top!=stk;__putc(*(--top)+'0'));
	}
 public:
	FastOutput(FILE *f=stdout): FastIOBase(f){}
#ifdef OPENIOBUF
	inline void setTarget(FILE *f) { this->flush(),target=f; }
	~FastOutput(){ flush(); }
#else
	inline void setTarget(FILE *f) { target=f; }
#endif
	template<typename ...T>
	inline void writesp(const T &...x)
		{ initializer_list<int>{(this->operator<<(x),__putc(' '),0)...}; }
	template<typename ...T>
	inline void writeln(const T &...x)
		{ initializer_list<int>{(this->operator<<(x),__putc('\n'),0)...}; }
	inline FastOutput &operator <<(char x)
		{ return __putc(x),*this; }
	inline FastOutput &operator <<(const char *s)
		{ for(;*s;__putc(*(s++)));return *this; }
	inline FastOutput &operator <<(const string &s)
		{ return (*this)<<s.c_str(); }
	template<typename T,typename=typename enable_if<is_integral<T>::value>::type>
	inline FastOutput &operator <<(const T &x)
		{ return __write(x),*this; }
}qout;

class FastInput: public FastIOBase
{
#ifdef OPENIOBUF
 public:
	inline void flush()
		{ buf[fread(buf,1,BUFSIZE,target)]='\0',buf_p=0; }
#endif
 protected:
	inline char __getc()
	{
#ifdef OPENIOBUF
		if(buf_p==BUFSIZE) flush();
		return buf[buf_p++];
#else
		return getc(target);
#endif
	}
 public:
#ifdef OPENIOBUF
	FastInput(FILE *f=stdin): FastIOBase(f){ buf_p=BUFSIZE; }
	inline void setTarget(FILE *f) { this->flush(),target=f; }
#else
	FastInput(FILE *f=stdin): FastIOBase(f){}
	inline void setTarget(FILE *f) { target=f; }
#endif
	inline char getchar() { return __getc(); }
	template<typename ...T>
	inline void read(T &...x)
		{ initializer_list<int>{(this->operator>>(x),0)...}; }
	inline FastInput &operator >>(char &x)
		{ while(isspace(x=__getc()));return *this; }
	template<typename T,typename=typename enable_if<is_integral<T>::value>::type>
	inline FastInput &operator >>(T &x)
	{
		static char ch,sym;x=sym=0;
		while(isspace(ch=__getc()));
		if(ch=='-') sym=1,ch=__getc();
		for(;isdigit(ch);x=(x<<1)+(x<<3)+(ch^48),ch=__getc());
		return sym?x=-x:x,*this;
	}
	inline FastInput &operator >>(char *s)
	{
		while(isspace(*s=__getc()));
		for(;!isspace(*s) && *s && ~*s;*(++s)=__getc());
		return *s='\0',*this;
	}
	inline FastInput &operator >>(string &s)
	{
		char str_buf[(1<<8)+1],*p=str_buf;
		char *const buf_end=str_buf+(1<<8);
		while(isspace(*p=__getc()));
		for(s.clear(),p++;;p=str_buf)
		{
			for(;p!=buf_end && !isspace(*p=__getc()) && *p && ~*p;p++);
			*p='\0',s.append(str_buf);
			if(p!=buf_end) break;
		}
		return *this;
	}
}qin;

} // namespace FastIO
using namespace FastIO;

using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;
constexpr LL INF=4e18;

#ifndef DADALZY
#define FILEIO(file) freopen(file".in","r",stdin),freopen(file".out","w",stdout)
#else
#define FILEIO(file)
#endif

int n,m,q,tot;
vector<pair<int,int>> g[200005];

struct TreeNode{ int v,w,lc,rc; }t[10000005];
int cnt,rt[400005];
#define LC t[i].lc
#define RC t[i].rc
void modify(int p,int v,int w,int &i,int l=1,int r=n)
{
	t[++cnt]=t[i],i=cnt;
	if(l==r) return t[i].v=v,(~w&&(t[i].w=w)),void();
	int mid=(l+r)>>1;
	if(mid>=p) modify(p,v,w,LC,l,mid);
	else modify(p,v,w,RC,mid+1,r);
	t[i].v=t[LC].v|t[RC].v;
}
int query(int p,int &i,int l=1,int r=n)
{
	if(l==r) return t[i].v;
	int mid=(l+r)>>1;
	if(mid>=p) return query(p,LC,l,mid);
	else return query(p,RC,mid+1,r);
}

struct ACNode{ int fail;map<int,int> ch; }t2[400005];
bool ban[400005],vis[400005];
LL dis[400005];
void build()
{
	queue<int> q;
	for(int i=1;i<=n;i++)
	{
		for(auto &[v,w]: g[i])
			modify(v,v,w,rt[i]);
		q.push(i),t2[i].fail=0;
	}
	while(!q.empty())
	{
		int u=q.front();q.pop();
		if(u>n) rt[u]=rt[t2[u].fail];
		ban[u]|=ban[t2[u].fail];
		for(auto &[c,v]: t2[u].ch)
		{
			modify(c,v,-1,rt[u]);
			if(!t2[u].fail) t2[v].fail=c;
			else t2[v].fail=query(c,rt[t2[u].fail]);
			q.push(v);
		}
	}
}
void dijkstra()
{
	priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<>> q;
	for(int i=0;i<=tot;i++) dis[i]=INF;
	q.emplace(dis[1]=0,1);
	function<void(int,LL,int,int)> update=[&update,&q](int i,LL d,int l,int r)
	{
		if(!t[i].v) return;
		if(l==r)
		{
			int v=t[i].v,w=t[i].w;
			if(!ban[v] && dis[v]>d+w) q.emplace(dis[v]=d+w,v);
			return t[i].v=0,void();
		}
		int mid=(l+r)>>1;
		update(LC,d,l,mid),update(RC,d,mid+1,r);
		t[i].v=t[LC].v|t[RC].v;
	};
	while(!q.empty())
	{
		auto &[d,u]=q.top();q.pop();
		if(vis[u] || ban[u]) continue;
		vis[u]=true,update(rt[u],d,1,n);
	}
}
int main()
{
	qin>>n>>m>>q;
	for(int i=1,u,v,w;i<=m;i++)
	{
		qin>>u>>v>>w;
		g[u].emplace_back(v,w);
	}
	for(int i=1;i<=n;i++) t2[0].ch[i]=++tot;
	for(int i=1,x,y,u;i<=q;i++)
	{
		qin>>x;
		for(u=0;x--;u=t2[u].ch[y])
		{
			qin>>y;
			if(t2[u].ch[y]) continue;
			t2[u].ch[y]=++tot;
		}
		ban[u]=true;
	}
	build(),dijkstra();
	qout<<(dis[n]<INF?dis[n]:-1);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 20
Accepted
time: 12ms
memory: 32052kb

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: -20
Wrong Answer
time: 8ms
memory: 32484kb

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:

2633887799

result:

wrong answer 1st lines differ - expected: '2296067497', found: '2633887799'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #11:

score: 30
Accepted
time: 168ms
memory: 90292kb

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: 180ms
memory: 88428kb

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: 179ms
memory: 89060kb

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: -30
Wrong Answer
time: 174ms
memory: 88892kb

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:

2562282398

result:

wrong answer 1st lines differ - expected: '2525861695', found: '2562282398'

Subtask #4:

score: 0
Skipped

Dependency #2:

0%