oj.uz

Submission #823739

# Submission time Handle Problem Language Result Execution time Memory
823739 2023-08-13T04:09:08 Z ttamx Stranded Far From Home (BOI22_island) C++14
0 / 100
 92 ms 7612 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 82 ms 7364 KB Output is correct
4 Incorrect 64 ms 7612 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 78 ms 7564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 92 ms 7400 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -