Submission #993970

#	Time	Username	Problem	Language	Result	Execution time	Memory
993970		MarwenElarbi	Stranded Far From Home (BOI22_island)	C++17	100 / 100	225 ms	45728 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e5+5;
vector<int> adj[nax];
vector<int> newadj[nax];
int tab[nax];
int parent[nax];
long long sz[nax];
int ans[nax];
int vis[nax];
int find(int x){
    if(parent[x]==x) return x;
    return parent[x]=find(parent[x]);
}
bool sameset(int x,int y){
    return find(x)==find(y);
}
void joinset(int x,int y){
    x=find(x);
    y=find(y);
    parent[x]=y;
    sz[y]+=sz[x];
}
bool compare(int x,int y){
    if(tab[x]!=tab[y]) return tab[x]>tab[y];
    else return x>y;
}
void dfs(int x,int p){
    //cout <<newadj[x].size()<<endl;
    for(auto u:newadj[x]){
        if(u==p) continue;
        if(sz[u]<tab[x]) continue;
        ans[u]=1;
        dfs(u,x);
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>> cur(n);
    for (int i = 0; i < n; ++i)
    {
        parent[i]=i;
        cin>>tab[i];
        sz[i]=tab[i];
        cur[i]={tab[i],i};
    }
    for (int i = 0; i < m; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    sort(cur.begin(),cur.end());
    for (int i = 0; i < n; ++i)
    {
        sort(adj[i].begin(),adj[i].end(),compare);
    }
    for (int t = 0; t < n; ++t)
    {
        int i=cur[t].se;
        vis[i]=true;
        for(auto u:adj[i]){
            u=find(u);
            //cout <<i<<" "<<u<<endl;
            if(!vis[u]||sameset(i,u)) continue;
            //cout <<i<<" "<<u<<" "<<sz[u]<<" "<<tab[i]<<endl;
            if(sz[u]>=tab[i]){
                newadj[i].pb(u);
            }
            joinset(u,i);
        }
        sz[i]=sz[find(i)];
    }
    ans[cur[n-1].se]=true;
    dfs(cur[n-1].se,-1);
    for (int i = 0; i < n; ++i)
    {
        cout <<ans[i];
    }cout <<endl;
}

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