Submission #654549

#	Time	Username	Problem	Language	Result	Execution time	Memory
654549		Lobo	Stranded Far From Home (BOI22_island)	C++17	100 / 100	178 ms	37036 KiB

island

#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;

int n, m, s[maxn], ds[maxn], dsz[maxn], dss[maxn], ans[maxn];
vector<int> win[maxn];

int find(int u) {
    if(u == ds[u]) return u;
    return ds[u] = find(ds[u]);
}

void join(int u, int v) {
    if(dsz[u] < dsz[v]) swap(u,v);
    dsz[u]+= dsz[v];
    dss[u]+= dss[v];
    ds[v] = u;
    for(auto x : win[v]) win[u].pb(x);
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> s[i];
        dss[i] = s[i];
        ds[i] = i;
        dsz[i] = 1;
        win[i].pb(i);
    }
    vector<pair<int,pair<int,int>>> edgs;
    for(int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;
        if(s[u] < s[v]) swap(u,v);
        edgs.pb(mp(s[u],mp(u,v)));
    }

    sort(all(edgs));
    for(auto X : edgs) {
        int smx = X.fr;
        int u = X.sc.fr;
        int v = X.sc.sc;

        if(dss[find(v)] < s[u]) {
            win[find(v)].clear();
        }
        if(find(u) != find(v)) join(find(u),find(v));
    }

    for(auto x : win[find(1)]) {
        ans[x] = 1;
    }
    for(int i = 1; i <= n; i++) {
        cout << ans[i];
    }cout << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Compilation message (stderr)

island.cpp: In function 'void solve()':
island.cpp:50:13: warning: unused variable 'smx' [-Wunused-variable]
   50 |         int smx = X.fr;
      |             ^~~

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