QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#771379#9431. The Quest for El Doradolijunrui08WA 83ms38028kbC++142.8kb2024-11-22 12:19:512024-11-22 12:19:52

Judging History

你现在查看的是最新测评结果

  • [2024-11-22 12:19:52]
  • 评测
  • 测评结果:WA
  • 用时:83ms
  • 内存:38028kb
  • [2024-11-22 12:19:51]
  • 提交

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'