QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#86244 | #5034. >.< | ExplodingKonjac | 0 | 217ms | 104828kb | C++17 | 5.8kb | 2023-03-09 16:12:53 | 2023-03-09 16:12:56 |
Judging History
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%