QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#771379 | #9431. The Quest for El Dorado | lijunrui08 | WA | 83ms | 38028kb | C++14 | 2.8kb | 2024-11-22 12:19:51 | 2024-11-22 12:19:52 |
Judging History
answer
#include <bits/stdc++.h>
#define fo(i,x,y) for(register int i=(x);i<=(y);i++)
#define de(i,x,y) for(register int i=(x);i>=(y);i--)
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const ll N=5e5+50,M=5e6+50,L=0;
const ll P=0,inf=1e9;
inline ll read(){
ll x=0;bool f=0;char c=getchar();
while(c<'0'||c>'9') f|=(c=='-'),c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return f?-x:x;
}
struct Edge{int v,c,d;};
struct node{int id;pii d;};
bool operator >(node a,node b){return a.d>b.d;}
int n,m,k,cntt;
int a[N],b[N],rt[N],suf[N],ls[M],rs[M],len[M],val[M],pri[M],mn[M],vis[N];
pii dis[N];
vector<Edge> G[N];
map<pii,int> pre;
int newn(int l,int v){
ls[cntt]=rs[cntt]=0;
len[++cntt]=l,val[cntt]=mn[cntt]=v;
pri[cntt]=rand()*rand();
return cntt;
}
void pushup(int id){mn[id]=min({mn[ls[id]],mn[rs[id]],val[id]});}
void split(int id,int w,int &l,int &r){
if(!id) return (void)(l=r=0);
if(len[id]<=w) l=id,split(rs[id],w,rs[l],r);
else r=id,split(ls[id],w,l,ls[r]);
pushup(id);
}
int merge(int l,int r){
if(!l||!r) return l+r;
if(pri[l]<pri[r]){
rs[l]=merge(rs[l],r);
return pushup(l),l;
}else{
ls[r]=merge(l,ls[r]);
return pushup(r),r;
}
}
int find(int c,int d){
int t1,t2;
split(rt[c],d-1,t1,t2);
int res=mn[t2]<inf?mn[t2]:-1;
return (void)(rt[c]=merge(t1,t2)),res;
}
priority_queue<node,vector<node>,greater<node>> q;
void dij(){
fo(i,1,n) vis[i]=0,dis[i]={inf,inf};
q.push({1,dis[1]={1,0}});
int lst=1;
while(!q.empty()){
int u=q.top().id;q.pop();
pii d=dis[u];
if(vis[u]++) continue;
while(lst<=d.fi){
int t1,t2,t3;
split(rt[a[lst]],b[lst]-1,t1,t2);
split(t2,b[lst],t2,t3);
if(suf[lst]) val[t2]=mn[t2]=suf[lst];
rt[a[lst]]=suf[lst]?merge(t1,t2):t1;
rt[a[lst]]=merge(rt[a[lst]],t3);
lst++;
}
for(Edge e:G[u]){
pii vd={inf,inf};
if(e.c==a[d.fi]&&b[d.fi]-d.se>=e.d) vd={d.fi,d.se+e.d};
else{
int nxt=find(e.c,e.d);
// if(u==2&&e.v==4) cout<<lst<<" "<<e.c<<" "<<e.d<<endl;
if(nxt!=-1) vd={nxt,e.d};
}
if(vd<dis[e.v]) dis[e.v]=vd,q.push({e.v,vd});
}
}
}
signed main(){
int T=read();
while(T--){
fo(i,1,m) suf[i]=rt[i]=0;
fo(i,1,n) G[i].clear();
pre.clear();
mn[0]=val[0]=inf;
n=read(),m=read(),k=read();
fo(i,1,m){
int u=read(),v=read(),c=read(),l=read();
G[u].push_back({v,c,l});
G[v].push_back({u,c,l});
}
fo(i,1,k){
a[i]=read(),b[i]=read();
if(pre[{a[i],b[i]}]) suf[pre[{a[i],b[i]}]]=i;
else{
int t1,t2;
split(rt[a[i]],b[i],t1,t2);
rt[a[i]]=merge(merge(t1,newn(b[i],i)),t2);
}
pre[{a[i],b[i]}]=i;
}
dij();
fo(i,1,n) printf("%d",!!vis[i]);
printf("\n");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 35684kb
input:
2 5 6 4 1 2 1 30 2 3 1 50 2 5 5 50 3 4 6 10 2 4 5 30 2 5 1 40 1 70 6 100 5 40 1 30 3 1 1 2 3 1 10 1 100
output:
11011 100
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 83ms
memory: 38028kb
input:
1110 46 80 30 44 23 5 46 10 28 1 64 32 34 3 40 9 36 1 26 15 14 5 95 38 19 2 34 2 17 4 183 10 38 2 81 5 15 2 83 31 38 3 100 40 30 1 53 41 10 1 193 29 20 5 18 14 41 3 78 8 16 5 74 46 13 3 78 44 28 3 45 1 40 3 133 5 32 1 108 22 26 2 83 10 38 1 77 11 40 1 11 17 21 2 66 41 46 3 98 9 36 2 25 40 18 1 19 27...
output:
1111111111111111111111111111111111111111111111 1111111111111111111111111111111111111111111111 1000000000000000000000000000000000000000000000 1111111111111111111111111111111111111111111111 1111111111111111111111111111111111111111111111 1001100010000000100001100000000011001110110 111111111111111111111...
result:
wrong answer 1st lines differ - expected: '1000110011110111110010100001010100100101000000', found: '1111111111111111111111111111111111111111111111'