Submission #881762

#	Time	Username	Problem	Language	Result	Execution time	Memory
881762		teesla	Stranded Far From Home (BOI22_island)	C++17	0 / 100	247 ms	50940 KiB

island

#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[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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35