제출 #644528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
644528		Tudy006	Stranded Far From Home (BOI22_island)	C++14	0 / 100	358 ms	32756 KiB

island

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e5;

pair <int, int> v[NMAX + 1];
int father[NMAX + 1];
bool viz[NMAX + 1];
vector <int> edges[NMAX + 1];
vector <int> children[NMAX + 1];

struct DSU {
    int father[NMAX + 1];
    void init() {
        for ( int i = 1; i <= NMAX; i ++ ) father[i] = i;
    }
    int root( int x ) {
        if ( father[x] == x ) return x;
        return ( father[x] = root( father[x] ) );
    }
    bool arejoined( int x, int y ) {
        return root( x ) == root( y );
    }
    void join( int x, int y ) {
        x = root( x );
        y = root( y );
        father[x] = y;
    }
};

int sum[NMAX + 1];
bool can[NMAX + 1];
int dfs_sum( int node ) {
    sum[node] = v[node].first;
    for ( auto it : children[node] ) {
        sum[node] += dfs_sum( it );
    }
    return sum[node];
}
void dfs_can( int node ) {
    if ( sum[node] >= v[father[node]].first && can[father[node]] == 1 ) can[node] = 1;
    for ( auto it : children[node] ) dfs_can( it );
}
bool cmp( pair <int, int> a, pair <int, int> b ) {
    return a.second < b.second;
}
int main() {
    int n, m, a, b;
    cin >> n >> m;
    for ( int i = 1; i <= n; i ++ ) {
        cin >> v[i].first;
        sum[i] = v[i].first;
        v[i].second = i;
    }
    for ( int i = 1; i <= m; i ++ ) {
        cin >> a >> b;
        edges[a].push_back( b );
        edges[b].push_back( a );
    }
    sort( v + 1, v + n + 1 );
    DSU dsu;
    dsu.init();
    for ( int i = 1; i <= n; i ++ ) {
        int node = v[i].second;
        viz[node] = true;
        for ( auto it : edges[node] ) {
            if ( viz[it] && !dsu.arejoined( node, it ) ) {
                father[dsu.root( it )] = node;
                children[node].push_back( dsu.root( it ) );
                dsu.join( dsu.root( it ), node );
            }
        }
    }
    int aux = v[n].second;
    sort( v + 1, v + n + 1, cmp );
    can[0] = 1;
    dfs_sum( aux );
    dfs_can( aux );
    for ( int i = 1; i <= n; i ++ ) cout << can[i];
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35