QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#723440#9431. The Quest for El DoradoUrabokuWA 34ms35136kbC++143.0kb2024-11-07 22:17:492024-11-07 22:17:49

Judging History

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

  • [2024-11-07 22:17:49]
  • 评测
  • 测评结果:WA
  • 用时:34ms
  • 内存:35136kb
  • [2024-11-07 22:17:49]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
#define O4 __inline__ __attribute__((always_inline))
#define inf 0x7fffffff
#define UL unsigned LL
#define LD long double
#ifdef ONLINE_JUDGE
#define getchar nc
#endif
//#define int LL
namespace FastIO{
	O4 char nc(){
		static char buf[100000],*p1=buf,*p2=buf;
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
	}
	O4 int read(){
		char t;int u=0,k=1;t=getchar();
		while(t<'0'||t>'9'){if(t==EOF)return -233;if(t=='-')k=-1;t=getchar();}
		while(t>='0'&&t<='9'){u=u*10+t-'0';t=getchar();}
		return u*k;
	}
	template <typename T>
	O4 void read(T &u){
		char t;T k=1;u=0;t=getchar();
		while(t<'0'||t>'9'){if(t=='-')k=-1;t=getchar();}
		while(t>='0'&&t<='9'){u=u*10+t-'0';t=getchar();}
		if(t=='.'){
			T mass=0.1;t=getchar();
			while(t>='0'&&t<='9'){u+=mass*(t-'0');mass/=10;t=getchar();}
		}u*=k;
	}
	O4 int read(char asd[]){
		char t=getchar();int u=0;
		while(t==' '||t=='\n'||t=='\r')t=getchar();
		if(t==EOF)return -1;
		while(t!=' '&&t!='\n'&&t!=EOF&&t!='\r')asd[u++]=t,t=getchar();
		asd[u]='\0';return u;
	}
	char sr[1<<23],z[23];int C=-1,Z;
	O4 void wer(int x,char T){
		int y=0;if(x<0)y=1,x=-x;
		while(z[++Z]=x%10+'0',x/=10);if(y)z[++Z]='-';
		while(sr[++C]=z[Z],--Z);sr[++C]=T;
	}
	O4 void wer(char T[],char QWQ){
		for(int i=0;T[i]!='\0';i++)sr[++C]=T[i];
		sr[++C]=QWQ;
	}
	O4 void out(){fwrite(sr,1,C+1,stdout);C=-1;}
}
using namespace std;
using namespace FastIO;
const int N=5e5+5;
int n,m,a,b,c,d,e,limit,k;
struct sss{
	int x,v;
	friend bool operator < (const sss &a,const sss &b){
		return a.v>b.v;
	}
}dist[N];
priority_queue <sss> hp,Z1;
struct ttt{
	int x,len;
	friend bool operator < (const ttt &a,const ttt &b){
		return a.len>b.len;
	}
};
priority_queue <ttt> load[N],Z2;
bool vis[N];
struct ooo{
	int to,com,len;
};
vector <ooo> MP[N],Z3;
void solve(){
	n=read();m=read();k=read();
	for(int i=1;i<=n;i++)MP[i]=Z3,vis[i]=0;
	hp=Z1;
	for(int i=1;i<=m;i++)load[i]=Z2;
	while(m--){
		a=read();b=read();c=read();d=read();
		MP[a].push_back((ooo){b,c,d});
		MP[b].push_back((ooo){a,c,d});
	}
	vis[1]=1;
	for(ooo i:MP[1]){
		load[i.com].push((ttt){i.to,i.len});
	}
	for(int GG=1;GG<=k;GG++){
		int c=read(),OVO=read();
		hp=Z1;
		while(!load[c].empty()){
			if(load[c].top().len>OVO)break;
			hp.push((sss){load[c].top().x,load[c].top().len});
			load[c].pop();
		}
		while(!hp.empty()){
			int x=hp.top().x,v=hp.top().v;
			hp.pop();
			if(vis[x])continue;
			vis[x]=1;
			for(ooo i:MP[x]){
				if(i.com!=GG||v+i.len>OVO){
					load[i.com].push((ttt){i.to,i.len});
				}
				else{
					hp.push((sss){i.to,v+i.len});
				}
			}
		}
//		cout<<GG<<"===================\n";
//		for(int i=1;i<=n;i++)cout<<vis[i];cout<<'\n';
	}
	for(int i=1;i<=n;i++)cout<<vis[i];cout<<'\n';
}
signed main(){
	int T=1;
	T=read();
	while(T--)solve();
}
/*
2

3 1 1
2 3 1 10
1 100

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

*/

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 34916kb

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: 34ms
memory: 35136kb

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:

1000100001100100010010000000010100000101000000
1100000010101011011011000000001000000100001000
1000000000000000000000000000000000000000000000
1011010000000010000100010011000100000000000010
1000000000000000000000001000010000000001000001
1001110110110000100101100000100011001110110
100010000000000000010...

result:

wrong answer 1st lines differ - expected: '1000110011110111110010100001010100100101000000', found: '1000100001100100010010000000010100000101000000'