oj.uz

Submission #942498

# Submission time Handle Problem Language Result Execution time Memory
942498 2024-03-10T18:19:43 Z alecurse Stranded Far From Home (BOI22_island) C++14
10 / 100
 238 ms 49076 KB 
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <unordered_set>
#define mp make_pair
#define ll long long int
using namespace std;
ll N, M;
vector<ll> link;
vector<ll> sizee;
vector<ll> realsizee;
vector<pair<ll,ll> > tosort;
vector<bool> vis;
vector<vector<ll> > adj;
vector<ll> v;
vector<bool> ans;
vector<ll> visiting;
vector<vector<ll> > tores;
map<ll,ll> neighbouring;
ll findd(ll x) {
    while(x!=link[x]) {
        x=link[x];
    }
    return x;
}
bool same(ll a, ll b) {
    return findd(a)==findd(b);
}


void unite(ll a, ll b) {
    a=findd(a);
    b=findd(b);
    if(sizee[b]>sizee[a]) swap(a,b);
    sizee[a]+=sizee[b];
    realsizee[a]+=realsizee[b];
    link[b]=a;
}

void visit(ll x) {
    if(vis[x]) return;
    vis[x]=true;
    visiting.push_back(x);
    for(auto b : adj[x]) {
        if(v[b]>v[x]) {
            neighbouring[v[b]]=b;
        } else if(v[b]==v[x]) {
            visit(b);
        }
        if(v[b]<=v[x]) {
            if(!same(x,b))
                unite(x,b);
        }
    }
}


int main() {
    cin>>N>>M;
    adj.resize(N);
    tores.resize(N);
    tosort.resize(N);
    vis.resize(N);
    v.resize(N);
    ans.resize(N);
    for(ll i=0;i<N;i++) {
        cin>>v[i];
        tosort[i]=mp(v[i],i);
    }
    sort(tosort.begin(),tosort.end());
    for(ll i=0;i<M;i++) {
        ll a,b;
        cin>>a>>b;
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    link.resize(N);
    realsizee.resize(N);
    sizee.assign(N,1);
    for(ll i=0;i<N;i++) {
        realsizee[i]=v[i];
        link[i]=i;
    }
    for(ll i=0;i<N;i++) {
        ll x=tosort[i].second;
        if(!vis[x]) {
            visit(x);
            ll llsize = realsizee[findd(x)];
            ll rrsize = sizee[findd(x)];
            if(rrsize==N) {
                for(auto el : visiting) {
                    ans[el]=1;
                }
            }
            auto it = neighbouring.upper_bound(llsize);
            if(it!=neighbouring.begin()) {
                it=prev(it,1);
                for(auto el : visiting) {
                    tores[(*it).second].push_back(el);
                }
            }
            neighbouring.clear();
            visiting.clear();

        }
    }
    for(ll i=N-1;i>=0;i--) {
        ll x = tosort[i].second;
        if(!ans[x]) continue;
        for(auto el : tores[x]) {
            ans[el]=1;
        }
    }
    for(ll i=0;i<N;i++) {
        cout<<ans[i];
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 2 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 211 ms 34520 KB Output is correct
4 Correct 183 ms 38344 KB Output is correct
5 Correct 210 ms 32516 KB Output is correct
6 Correct 215 ms 33616 KB Output is correct
7 Correct 238 ms 33708 KB Output is correct
8 Correct 214 ms 35528 KB Output is correct
9 Correct 208 ms 33104 KB Output is correct
10 Correct 179 ms 30968 KB Output is correct
11 Correct 180 ms 33396 KB Output is correct
12 Correct 190 ms 30052 KB Output is correct
13 Correct 204 ms 49076 KB Output is correct
14 Correct 181 ms 47008 KB Output is correct
15 Correct 223 ms 36432 KB Output is correct
16 Correct 169 ms 35156 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 235 ms 31056 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 238 ms 31852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 2 ms 604 KB Output isn't correct
5 Halted 0 ms 0 KB -