제출 #1203491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203491		AlgorithmWarrior	Stranded Far From Home (BOI22_island)	C++20	0 / 100	185 ms	14820 KiB

island

#include <bits/stdc++.h>

using namespace std;

int const MAX=200005;
int n,m;
int v[MAX];
vector<int>G[MAX];
int tata[MAX];
bool val[MAX];
int perm[MAX];
int sz[MAX];

bool crt(int a,int b){
    if(v[a]!=v[b])
        return v[a]<v[b];
    return a<b;
}

void read(){
    cin>>n>>m;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i];
    for(i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
}

pair<int,bool>find_root(int nod){
    if(nod==tata[nod])
        return {nod,1};
    pair<int,bool>ans=find_root(tata[nod]);
    val[nod]&=ans.second;
    tata[nod]=ans.first;
    return {tata[nod],val[nod]};
}

void solve(){
    int i;
    for(i=1;i<=n;++i)
        perm[i]=i;
    sort(perm+1,perm+n+1,crt);
    for(i=1;i<=n;++i){
        int nod=perm[i];
        tata[nod]=nod;
        val[nod]=1;
        sz[nod]=v[nod];
        for(auto vec : G[nod])
            if(crt(vec,nod)){
                int root=find_root(vec).first;
                if(root!=nod){
                    if(sz[root]<v[nod])
                        val[root]=0;
                    tata[root]=nod;
                    sz[nod]+=sz[root];
                }
            }
    }
}

void write(){
    int i;
    for(i=1;i<=n;++i){
        find_root(i);
        cout<<(val[i]&val[tata[i]]);
    }
}

int main()
{
    read();
    solve();
    write();
    return 0;
}

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