제출 #942498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
942498		alecurse	Stranded Far From Home (BOI22_island)	C++14	10 / 100	238 ms	49076 KiB

island

#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
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35