oj.uz

Submission #828253

# Submission time Handle Problem Language Result Execution time Memory
828253 2023-08-17T07:18:39 Z Pacybwoah Stranded Far From Home (BOI22_island) C++17
0 / 100
 323 ms 40072 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#define ll long long
using namespace std;
vector<int> dsu,sz,ans;
vector<ll> sum;
vector<set<int> > nodes;
void build(int n){
    dsu.resize(n+1);
    sz.resize(n+1);
    for(int i=1;i<=n;i++) dsu[i]=i,sz[i]=1,nodes[i].insert(i);
}
int query(int x){
    if(dsu[x]==x) return x;
    return query(dsu[x]);
}
void unite(int a,int b){
    a=query(a),b=query(b);
    if(a==b) return;
    if(sz[a]<sz[b]) swap(a,b);
    dsu[b]=a;
    sz[a]+=sz[b];
    sum[a]+=sum[b];
    for(auto x:nodes[b]) if(ans[x]==-1) nodes[a].insert(x);
    nodes[b].clear();
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector<vector<int> > graph;
    ans.resize(n+1,-1);
    nodes.resize(n+1);
    graph.resize(n+1);
    sum.resize(n+1);
    vector<pair<ll,int> > val(n);
    for(int i=1;i<=n;i++) cin>>val[i-1].first,val[i-1].second=i,sum[i]=val[i-1].first;
    int a,b;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        if(val[a-1]<val[b-1]) graph[b].push_back(a);
        else graph[a].push_back(b);
    }
    sort(val.begin(),val.end());
    build(n);
    for(int i=0;i<n;i++){
        for(auto x:graph[val[i].second]){
            unite(x,val[i].second);
        }
        int mum=query(val[i].second);
        if(i!=n-1&&sum[mum]<val[i+1].first){
            for(auto x:nodes[mum]){
                //cout<<val[i].second<<" "<<x<<"\n";
                ans[x]=0;
            }
            nodes[mum].clear();
        }
    }
    for(int i=1;i<=n;i++){
        if(ans[i]==-1) cout<<1;
        else cout<<0;
    }
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 136 ms 39800 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 212 KB Output is correct
2 Incorrect 297 ms 39376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 323 ms 40072 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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