oj.uz

Submission #881763

# Submission time Handle Problem Language Result Execution time Memory
881763 2023-12-01T20:50:13 Z teesla Stranded Far From Home (BOI22_island) C++17
0 / 100
 907 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> ii;
typedef pair<int,ii> iii;


int n,m;
vector<priority_queue<ii,vector<ii>, greater<ii>>>adj;
priority_queue<ii,vector<ii>, greater<ii>> q;
vector<int> v,poder;

vector<set<int>> ok;

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    v.assign(n+2,0); adj.resize(n+2);
    poder.assign(n+2,0);
    ok.resize(n+2);

    for(int i=1; i<=n; i++){
        int a; cin >> a; v[i] = a;
        poder[i] = a;
        ok[i].insert(i);// saber quem tá no grupo de quem no final // lista valida
        q.push({a, i});// valor indice
    }

    for(int i=0; i<m; i++){
        int a, b; cin >> a >> b;
        adj[a].push({v[b], b});
        adj[b].push({v[a], a});
    }

    vector<int> vis(n+2,0);

    int ant = 0;

    while(!q.empty()){

        auto [a,b] = q.top(); q.pop();
        if(vis[b] == 1) continue;
        if(poder[b] != a) continue;
        vis[b] = 1;ant = b;

        bool blz = 1;
        while(!adj[b].empty() and blz){
            
            auto [aa, bb] = adj[b].top(); adj[b].pop();
            if(vis[bb]) continue;
            blz = 0;

            if(poder[b] >= aa){ // add na resposta (b compartilha a mesma resposta bb)
                if(ok[b].size() > ok[bb].size()) swap(ok[b], ok[bb]);
                for(auto i: ok[b]) ok[bb].insert(i);
            }

            poder[bb] += a;
            q.push({poder[bb], bb});

            if(adj[b].size() > adj[bb].size()) swap(adj[b], adj[bb]);

            while(!adj[b].empty()){ //small to large para redirecionar as arestas
                adj[bb].push(adj[b].top());
                adj[adj[b].top().second].push({v[bb], bb});
                adj[b].pop();
            }
        }
    }

    vector<int> res(n+2);

    for(auto i: ok[ant]){
        res[i] = 1;
    }

    for(int i = 1; i<=n; i++) cout << res[i];
    cout << endl;

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 700 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 692 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 907 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 681 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Runtime error 700 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -