oj.uz

Submission #1041234

# Submission time Handle Problem Language Result Execution time Memory
1041234 2024-08-01T18:35:15 Z Maite_Morale Stranded Far From Home (BOI22_island) C++17
25 / 100
 1000 ms 524288 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=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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24664 KB Output is correct
2 Correct 5 ms 24668 KB Output is correct
3 Correct 4 ms 24668 KB Output is correct
4 Runtime error 309 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24764 KB Output is correct
2 Correct 4 ms 24884 KB Output is correct
3 Correct 344 ms 55796 KB Output is correct
4 Correct 329 ms 60344 KB Output is correct
5 Correct 344 ms 58320 KB Output is correct
6 Correct 413 ms 59360 KB Output is correct
7 Correct 341 ms 59544 KB Output is correct
8 Correct 336 ms 63060 KB Output is correct
9 Correct 288 ms 58452 KB Output is correct
10 Correct 196 ms 55188 KB Output is correct
11 Correct 253 ms 62912 KB Output is correct
12 Correct 290 ms 59728 KB Output is correct
13 Correct 243 ms 61696 KB Output is correct
14 Correct 290 ms 61780 KB Output is correct
15 Correct 270 ms 62288 KB Output is correct
16 Correct 184 ms 61184 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24664 KB Output is correct
2 Correct 300 ms 53920 KB Output is correct
3 Correct 309 ms 54096 KB Output is correct
4 Correct 317 ms 57900 KB Output is correct
5 Correct 249 ms 59100 KB Output is correct
6 Correct 316 ms 58476 KB Output is correct
7 Correct 293 ms 62292 KB Output is correct
8 Correct 281 ms 62292 KB Output is correct
9 Correct 179 ms 61268 KB Output is correct
10 Correct 243 ms 59732 KB Output is correct
11 Correct 268 ms 56916 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24668 KB Output is correct
2 Execution timed out 1117 ms 518476 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24664 KB Output is correct
2 Correct 5 ms 24668 KB Output is correct
3 Correct 4 ms 24668 KB Output is correct
4 Runtime error 309 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -