oj.uz

Submission #975045

# Submission time Handle Problem Language Result Execution time Memory
975045 2024-05-04T10:36:30 Z vjudge1 Stranded Far From Home (BOI22_island) C++17
0 / 100
 79 ms 8620 KB 
#include<bits/stdc++.h>
using namespace std;
const int NN=2e5+1;
long long node[NN],sum[NN];
int par[NN];
bitset<NN> ans;
int fp(int i){
    if(i==par[i]) return i;
    int p=fp(par[i]);
    if(!ans[par[i]]) ans[i]=ans[par[i]];
    par[i]=p;
    return p;
}
struct edl
{
    int a,b;
    bool operator < (const edl &rhs) const{
        return max(node[a],node[b])<max(node[rhs.a],node[rhs.b]);
    }
};
vector<edl> v;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m,a,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {cin>>node[i],par[i]=i; sum[i]=node[i];}
    while(m--){
        cin>>a>>b;
        v.push_back({a,b});
    }
    sort(v.begin(),v.end());
    ans.set();
    for(auto i:v){
        int p1=fp(i.a);
        int p2=fp(i.b);
        if(p1==p2) continue;
        // cout<<p1<<" "<<p2<<"\n";
        if(node[p1]<node[p2]) swap(p1,p2);
        if(sum[p1]>sum[p2]) ans[p2]=0;
        par[p2]=p1;
        sum[p1]+=sum[p2];
    }
    for(int i=1;i<=n;i++){
        fp(i);
        cout<<ans[i];
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2524 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 77 ms 8620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 79 ms 6348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 79 ms 6528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2524 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Halted 0 ms 0 KB -