QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#86453 | #5034. >.< | XZTmaxsmall67 | 0 | 204ms | 96668kb | C++23 | 2.6kb | 2023-03-09 21:55:47 | 2023-03-09 21:55:49 |
Judging History
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;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 9ms
memory: 28664kb
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: 204ms
memory: 96668kb
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%