oj.uz

Submission #1041237

# Submission time Handle Problem Language Result Execution time Memory
1041237 2024-08-01T18:41:30 Z Maite_Morale Stranded Far From Home (BOI22_island) C++17
0 / 100
 312 ms 53844 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23900 KB Output is correct
2 Correct 7 ms 23788 KB Output is correct
3 Correct 8 ms 23900 KB Output is correct
4 Incorrect 8 ms 24176 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23896 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Incorrect 293 ms 53844 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23896 KB Output is correct
2 Incorrect 293 ms 48828 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23900 KB Output is correct
2 Incorrect 312 ms 52428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23900 KB Output is correct
2 Correct 7 ms 23788 KB Output is correct
3 Correct 8 ms 23900 KB Output is correct
4 Incorrect 8 ms 24176 KB Output isn't correct
5 Halted 0 ms 0 KB -