제출 #1041237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041237		Maite_Morale	Stranded Far From Home (BOI22_island)	C++17	0 / 100	312 ms	53844 KiB

island

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define MAX 500005
#define pll pair<ll,ll>
#define F first
#define S second

vll v[MAX],r[MAX];
ll n,m,t,k,a[MAX],p[MAX],ans[MAX];
pll ord[MAX];
ll fnd(ll x){
  //  cout<<x<<p[x]<<"{\n";
    if(p[x]==x){
       // cout<<x<<"}\n";
        return p[x];
    }
    p[x]=fnd(p[x]);
   // cout<<x<<"}\n";
return p[x];
}
void uni(ll x,ll y){
    x=fnd(x);y=fnd(y);
    if(fnd(x)==fnd(y))return;
    a[y]+=a[x];
    p[x]=y;
}
int main(){
    cin>>n>>m;map<ll,ll> mp;
    for(int i=1;i<=n;i++){
        cin>>a[i];p[i]=i;
        ord[i]={a[i],i};
    }
    sort(ord+1,ord+n+1);
    for(int i=1;i<=n;i++){
        mp[ord[i].S]=i;
        a[i]=ord[i].F;
    }
    ll a1,a2;
    for(int i=0;i<m;i++){
        cin>>a1>>a2;
        a1=mp[a1];a2=mp[a2];
        v[a1].push_back(a2);
        v[a2].push_back(a1);
    }
    for(int i=1;i<=n;i++){
        for(auto u : v[i]){
            if(i<=u)continue;
            ll x=fnd(u);
            if(a[x]>=a[i] && ans[x]==0){
                ans[x]=1;
                r[i].push_back(x);
            }
        }
        for(auto u : v[i]){
            if(i<=u)continue;
            ll x=fnd(u);
            if(ans[x]==0)continue;
            uni(x,i);ans[x]=0;
        }
    }
    queue<ll> q;q.push(n);
    while(!q.empty()){
        ll u=q.front();q.pop();
        ans[ord[u].S]=1;
        for(auto w : r[u]){
            if(ans[ord[w].S]==0)q.push(w);
        }
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i];
    }
return 0;
}

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