QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #572492 | #4209. Stranded Far From Home | hansiyuan | 0 | 80ms | 17240kb | C++14 | 835b | 2024-09-18 14:55:39 | 2024-09-18 14:55:42 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+5;
int n,m;
int siz[N],fa[N],fail[N];
struct nd{int u,v,w;} e[N];
bool cmp(nd x,nd y){return x.w<y.w;}
int getfa(int x){
if(x==fa[x]) return x;
int fath = getfa(fa[x]);
fail[x] |= fail[fa[x]];
return fath;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&siz[i]);
fa[i] = i;
}
for(int i=1;i<=m;i++){
scanf("%lld%lld",&e[i].u,&e[i].v);
if(siz[e[i].u]<siz[e[i].v])
swap(e[i].u,e[i].v);
e[i].w = siz[e[i].u];
}
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++){
int x=e[i].u,y=e[i].v;
int fx=getfa(x),fy=getfa(y);
if(siz[fy]<siz[fx]) fail[fy]=1;
siz[fx] += siz[fy];
fa[fy] = fx;
}
for(int i=1;i<=n;i++){
getfa(i);
printf("%d",!fail[i]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 10172kb
input:
1622 1998 29021716 740464354 721037601 759718475 973636178 59068917 294028640 285332651 203821680 397646208 488684783 448548424 565347277 112938323 832704692 837437153 508335516 167646888 798998153 86605661 820823253 705498382 116513873 672806499 522392461 568294614 457655230 647498964 577669416 506...
output:
000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000...
result:
wrong answer 1st lines differ - expected: '011110101110001100101101111110...1000100110101000000111111011011', found: '000000000000000000000000000000...0000000000000000000000000000000'
Subtask #2:
score: 0
Wrong Answer
Test #15:
score: 10
Accepted
time: 59ms
memory: 17240kb
input:
200000 199999 100000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok single line: '100000000000000000000000000000...0000000000000000000000000000000'
Test #16:
score: 0
Wrong Answer
time: 80ms
memory: 16724kb
input:
200000 199999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer 1st lines differ - expected: '111111111111111111111111111111...0000000000000000000000000000000', found: '000000000000000000000000000000...0000000000000000000000000000000'
Subtask #3:
score: 0
Time Limit Exceeded
Test #30:
score: 0
Time Limit Exceeded
input:
199999 199998 758475118 758475116 758475114 758475112 758475110 758475108 758475106 758475104 758475102 758475100 758475098 758475096 758475094 758475092 758475090 758475088 758475086 758475084 758475082 758475080 758475078 758475076 758475074 758475072 758475070 758475068 758475066 758475064 758475...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #39:
score: 0
Time Limit Exceeded
input:
155555 200000 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%