QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#86256 | #5034. >.< | ExplodingKonjac | 0 | 180ms | 90292kb | C++17 | 5.7kb | 2023-03-09 16:22:33 | 2023-03-09 16:22:34 |
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{ 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%