Submission #938065

#	Time	Username	Problem	Language	Result	Execution time	Memory
938065		LucaIlie	Stranded Far From Home (BOI22_island)	C++17	100 / 100	709 ms	103356 KiB

island

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;
bool active[MAX_N + 1], sePoate[MAX_N + 1];
int s[MAX_N + 1];
vector<int> adj[MAX_N + 1];
map<long long, vector<int>> updates, queries;
priority_queue<long long> times;

struct DSU {
    int n;
    vector<int> sef, sz;
    vector<long long> sum;

    void init( int _n ) {
        n = _n;
        sef.resize( n );
        sz.resize( n );
        sum.resize( n );
        for ( int u = 0; u < n; u++ ) {
            sef[u] = u;
            sz[u] = 1;
            sum[u] = s[u];
        }
    }

    int findSef( int v ) {
        if ( sef[v] == v )
            return v;
        sef[v] = findSef( sef[v] );
        return sef[v];
    }

    int calcSz( int v ) {
        return sz[findSef( v )];
    }

    long long calcSum( int v ) {
        return sum[findSef( v )];
    }

    void unionn( int u, int v ) {
        u = findSef( u );
        v = findSef( v );
        if ( sz[u] > sz[v] )
            swap( u, v );

        if ( u == v )
            return;


        sef[u] = v;
        sz[v] += sz[u];
        sum[v] += sum[u];
    }
} orase;

int main() {
    int n, m;

    cin >> n >> m;
    for ( int v = 1; v <= n; v++ )
        cin >> s[v];
    for ( int i = 0; i < m; i++ ) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    for ( int v = 1; v <= n; v++ ) {
        updates[s[v]].push_back( v );
        queries[s[v]].push_back( v );
        times.push( -s[v] );
    }

    orase.init( n + 1 );
    long long prvT = -1;
    while ( !times.empty() ){
        long long t = -times.top();
        times.pop();

        if ( t == prvT )
            continue;

        for ( int u: updates[t] ) {
            active[u] = true;
            for ( int v: adj[u] ) {
                if ( active[v] )
                    orase.unionn( u, v );
            }
        }

        for ( int v: queries[t] ) {
            int sz = orase.calcSz( v );
            long long sum = orase.calcSum( v );
            if ( sz == n )
                sePoate[v] = true;
            else if ( sum > t ) {
                queries[sum].push_back( v );
                times.push( -sum );
            }
        }
        
        prvT = t;
    }

    for ( int v = 1; v <= n; v++ )
        cout << sePoate[v];

    return 0;
}

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