oj.uz

Submission #938064

# Submission time Handle Problem Language Result Execution time Memory
938064 2024-03-04T19:04:53 Z LucaIlie Stranded Far From Home (BOI22_island) C++17
0 / 100
 1000 ms 128536 KB 
#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<int, vector<int>> updates, queries;
priority_queue<int> 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 );
    int prvT = -1;
    while ( !times.empty() ){
        int 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 );
            }
        }
    }

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

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Runtime error 7 ms 11100 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Runtime error 276 ms 121284 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Runtime error 468 ms 128536 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Execution timed out 1069 ms 82204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Runtime error 7 ms 11100 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -