Submission #823739

#	Time	Username	Problem	Language	Result	Execution time	Memory
823739		ttamx	Stranded Far From Home (BOI22_island)	C++14	0 / 100	92 ms	7612 KiB

island

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int,int> p2;
typedef tuple<int,int,int> t3;

const int N=2e5+5;

int n,m;
int s[N],fa[N],ans[N];
ll sum,sz[N];
vector<t3> edge;

int fp(int u){
    if(u==fa[u])return u;
    return fa[u]=fp(fa[u]);
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1;i<=n;i++)cin >> s[i];
    for(int i=1;i<=n;i++){
        fa[i]=i;
        sz[i]=s[i];
        ans[i]=1;
        sum+=s[i];
    }
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        edge.emplace_back(max(s[u],s[v]),u,v);
    }
    sort(edge.begin(),edge.end());
    for(auto [w,u,v]:edge){
        int pu=fp(u),pv=fp(v);
        if(pu==pv)continue;
        if(sz[pu]<w)ans[u]=0;
        if(sz[pv]<w)ans[v]=0;
        fa[pv]=pu;
        sz[pu]+=sz[pv];
    }
    for(int i=1;i<=n;i++)cout << (ans[i]&&(sz[fp(i)]==sum));
}

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:38:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     for(auto [w,u,v]:edge){
      |              ^

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