Submission #640463

#	Time	Username	Problem	Language	Result	Execution time	Memory
640463		makanhulia	Stranded Far From Home (BOI22_island)	C++17	10 / 100	232 ms	52332 KiB

island

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ii pair<int,int>
using namespace std;

const int dv = 1e9 + 7;
const int sz = 1e5;

int n, m, vtd[2*sz+5], p[2*sz+5], idx, trav;

vector<int> adj[2*sz+5], v[2*sz+5];
ll cnt[2*sz+5];

void dfs(int node) {
    cnt[node] = p[node];
    vtd[node] = 1;
    v[node].push_back(node);
    for(auto i : adj[node]) {
        if(!vtd[i]) {
            dfs(i);
            if(cnt[i] >= p[node]) {
                if(v[i].size() > v[node].size()) swap(v[node], v[i]);
                for(int j : v[i]) v[node].push_back(j);
            }
            cnt[node] += cnt[i];
        }
    }
}

int ans[2*sz+5];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n ;++i) {
        cin >> p[i];
    }
    for(int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1);
    for(auto i: v[1]) ans[i] = 1;
    for(int i = 1; i <= n; ++i) cout << ans[i];
}

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