Submission #1279782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279782		wonderful	Stranded Far From Home (BOI22_island)	C++20	0 / 100	171 ms	50328 KiB

island

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()

template<class T1, class T2>
bool maximize(T1 &a, T2 b){ if (a < b){ a = b; return true; } return false; }

template<class T1, class T2>
bool minimize(T1 &a, T2 b){ if (a > b){ a = b; return true; } return false; }

const ll INF = 1e18;

int n, m;
ll t[1000005];
vector<int> adj[1000005];
pair<int,int> edges[1000005];

bool vis[1000005];
int par[1000005];
int mark[1000005];
int cur, root;
int child[1000005];
bool vis1[1000005];

vector<int> tree1[1000005], tree2[1000005];

bool cmp(pair<int,int> a, pair<int,int> b){
    return max(t[a.first], t[a.second]) < max(t[b.first], t[b.second]);
}

void predfs(int u){
    vis[u] = true;
    for (auto v : adj[u]){
        if (!vis[v]) predfs(v);
    }
}

int findSet(int u){
    if (par[u] == u) return u;
    return par[u] = findSet(par[u]);
}

void join(int u, int v, int val){
    u = findSet(u);
    v = findSet(v);
    if (u == v) return;
    cur++;
    root = cur;
    mark[cur] = val;
    par[u] = par[v] = cur;
    tree1[cur].push_back(u);
    tree1[cur].push_back(v);
}

void dfs(int u){
    if (u <= n){
        child[u] = t[u];
        return;
    }
    for (auto v : tree1[u]){
        dfs(v);
        child[u] += child[v];
        if (child[v] >= mark[u]){
            tree2[u].push_back(v);
        }
    }
}

void dfs1(int u){
    vis1[u] = true;
    for (auto v : tree2[u]){
        dfs1(v);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);



    cin >> n >> m;
    root=n;
    for (int i = 1; i <= n; i++) cin >> t[i];

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

    predfs(1);
    for (int i = 1; i <= n; i++){
        if (!vis[i]){
            for (int j = 1; j <= n; j++) cout << 0;
            return 0;
        }
    }

    sort(edges + 1, edges + 1 + m, cmp);
    cur = n;
    for (int i = 1; i <= m+n+5; i++) par[i] = i;

    for (int i = 1; i <= m; i++){
        join(edges[i].first, edges[i].second, max(t[edges[i].first], t[edges[i].second]));
    }

    dfs(root);
    dfs1(root);

    string res;
    for (int i = 1; i <= n; i++){
        res.push_back(vis1[i] ? '1' : '0');
    }
    cout << res << "\n";

    return 0;
}

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