oj.uz

답안 #828281

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
828281 2023-08-17T07:38:38 Z Pacybwoah Stranded Far From Home (BOI22_island) C++17
0 / 100
 281 ms 40344 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;){
        int now=i;
        while(now<n&&val[i].first==val[now].first){
            for(auto x:graph[val[now].second]){
                unite(val[now].second,x);
            }
            now++;
        }
        if(now==n) break;
        for(int j=i;j<now;j++){
            int mum=query(val[j].second);
            if(sum[mum]<val[now].first){
                for(auto x:nodes[mum]){
                    ans[x]=0;
                }
                nodes[mum].clear();
            }
        }
        i=now;
    }
    for(int i=1;i<=n;i++){
        if(ans[i]==-1) cout<<1;
        else cout<<0;
    }
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Incorrect 2 ms 584 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 124 ms 39780 KB Output is correct
4 Correct 134 ms 40344 KB Output is correct
5 Incorrect 262 ms 38140 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 263 ms 35464 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 324 KB Output is correct
2 Incorrect 281 ms 35276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Incorrect 2 ms 584 KB Output isn't correct
5 Halted 0 ms 0 KB -