oj.uz

Submission #644528

# Submission time Handle Problem Language Result Execution time Memory
644528 2022-09-24T20:24:13 Z Tudy006 Stranded Far From Home (BOI22_island) C++14
0 / 100
 358 ms 32756 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10424 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 6 ms 10488 KB Output is correct
4 Incorrect 9 ms 10672 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Incorrect 358 ms 29200 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10424 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 6 ms 10488 KB Output is correct
4 Incorrect 9 ms 10672 KB Output isn't correct
5 Halted 0 ms 0 KB -