Submission #722915

#	Time	Username	Problem	Language	Result	Execution time	Memory
722915		sunnat	Stranded Far From Home (BOI22_island)	C++14	100 / 100	417 ms	47176 KiB

island

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define int long long
int n;
vector<int> val, sid, id, root, solution;

vector<vector<int> > graph;
vector<vector<int> > tree;

int dsu(int u){
    return root[u] == u ? u : root[u] = dsu(root[u]);
}
void clear_sub_tree(int u){
    if(solution[u] == 0) return;
    solution[u] = 0;
    for(int v:tree[u]) clear_sub_tree(v);
}
void dfs(int u){
    int vl = val[u];
    // cout << "-->" << u << endl;
    for(int v:tree[u]){
        dfs(v);
        val[u] += val[v];
        if(val[v] < vl) clear_sub_tree(v);
    }
    // cout << "<--" << u << endl;
}

signed main(){
    int m;
    cin >> n >> m;
    val.resize(n);
    graph.resize(n);
    tree.resize(n);
    sid.resize(n);
    id.resize(n);
    solution.resize(n, 1);
    
    for(int i = 0; i < n; i ++){
        cin >> val[i];
        sid[i] = i;
    }
    root = sid;
    sort(sid.begin(), sid.end(), [&](int r, int l){return val[r] < val[l];});
    for(int i = 0; i < n; i ++)
        id[sid[i]] = i;

    for(int i = 0, u, v; i < m; i ++){
        cin >> u >> v;
        --u;
        --v;
        if(id[u] > id[v]) swap(u, v);
        graph[v].push_back(u);
    }

    for(int u:sid){
        for(int v:graph[u]){
            if(dsu(u) != dsu(v)){
                tree[u].push_back(dsu(v));
                root[dsu(v)] = u;
            }
        }
    }
    dfs(sid.back());
    for(int x:solution) cout << x;
    return 0;
}

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