QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#723440 | #9431. The Quest for El Dorado | Uraboku | WA | 34ms | 35136kb | C++14 | 3.0kb | 2024-11-07 22:17:49 | 2024-11-07 22:17:49 |
Judging History
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'