Submission #1041234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041234		Maite_Morale	Stranded Far From Home (BOI22_island)	C++17	25 / 100	1117 ms	524288 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=u;
            x=fnd(x);
            if(a[x]>=a[i]){
                r[i].push_back(x);
               // cout<<i<<"->"<<x<<"\n";
            }
        }
        for(auto u : v[i]){
            if(i<=u)continue;
            uni(u,i);
        }
    }
    queue<ll> q;q.push(n);
    while(!q.empty()){
        ll u=q.front();q.pop();
        ans[ord[u].S]=1;
       // cout<<u<<"\n";
        for(auto w : r[u]){
            if(ans[ord[w].S]==0)q.push(w);
        }
    }
   // cout<<"//////////////////////////\n";
    for(int i=1;i<=n;i++){
        cout<<ans[i];
    }
return 0;
}

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