QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#86244#5034. >.<ExplodingKonjac0 217ms104828kbC++175.8kb2023-03-09 16:12:532023-03-09 16:12:56

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:12:56]
  • 评测
  • 测评结果:0
  • 用时:217ms
  • 内存:104828kb
  • [2023-03-09 16:12:53]
  • 提交

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{ bool has;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)),t[i].has=true,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].has=t[LC].has|t[RC].has;
}
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].has) return;
		if(l==r)
		{
			int v=t[i].v,w=t[i].w;
			if(!ban[v]) q.emplace(dis[v]=d+w,v);
			return t[i].has=false,void();
		}
		int mid=(l+r)>>1;
		update(LC,d,l,mid),update(RC,d,mid+1,r);
		t[i].has=t[LC].has|t[RC].has;
	};
	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;
}
/*
7 8 2
1 2 1
2 3 2
3 4 1
4 5 1
4 6 1
5 7 1
6 7 1
6 5 2
6 1 2 3 4 5 7
5 2 3 4 6 7

*/

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 12ms
memory: 31356kb

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:

2956910940

result:

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

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 217ms
memory: 104828kb

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:

3359979153

result:

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

Subtask #4:

score: 0
Skipped

Dependency #2:

0%