Submission #993773

#	Time	Username	Problem	Language	Result	Execution time	Memory
993773		MarwenElarbi	Stranded Far From Home (BOI22_island)	C++17	0 / 100	1067 ms	524288 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;
set<pair<int,int>> revadj[nax];
vector<int> adj[nax];
bool vis[nax];
int tab[nax];
bool state[nax];
long long sz[nax];
int res[nax];
vector<int> top;
bool compare(int x,int y){
  return tab[x]<tab[y];
}
/*struct node{
  int child,par,x,p;
};
struct compare2{
  bool operator()(node const& p1, node const& p2)
    {
        if(p1.child!=p2.child) return p1.child < p2.child;
        else return p1.par > p2.par;
    }
};
void top_sort(int x){
  vis[x]=true;
  for(auto u:adj[x])
  {
    if(vis[u]) continue;
    top_sort(x);
  }
  top.pb(x);
}*/

void dfs(int x,int p){
  sz[x]=tab[x];
  for(auto u:adj[x]){
    if(u==p) continue;
    dfs(u,x);
    sz[x]+=sz[u];
  }
  if(p!=-1){
    if(sz[x]>=tab[p]) state[x]=1;
    else state[x]=0;
  }
}
void ans(int x,int p){
  if(state[x]==0) return;
  res[x]=1;
  for(auto u:adj[x]){
    if(u==p) continue;
    ans(u,x);
  }
}
int main() {
    int n,m;
    cin>>n>>m;
    pair<int,int> mx={-1,-1};
    vector<pair<int,int>> cur(n);
    for (int i = 0; i < n; ++i)
    {
        cin>>tab[i];
        cur[i]={tab[i],i};
        if(mx.fi<tab[i]){
          mx={tab[i],i};
        }
    }
    for (int i = 0; i < m; ++i)
    {
      int x,y;
      cin>>x>>y;
      x--;y--;
      if(tab[x]==tab[y]){
        revadj[x].insert({tab[y],y});
        revadj[y].insert({tab[x],x});
      }else if(tab[x]>tab[y]){
        revadj[y].insert({tab[x],x});
      }else{
        revadj[x].insert({tab[y],y});
      }
    }
    sort(cur.begin(),cur.end());
    set<pair<int,int>> nab;
    int j=0;
    for (int i = 0; i < n-1; ++i)
    {
      if(vis[i]) continue;
      set<int> a;
      int b=cur[j].se;
      a.insert(b);
      j++;
      for(auto u:revadj[b]){
        if(a.count(u.se)) continue;
        nab.insert(u);
      }
      while(true){
        for(auto u:revadj[b]){
          if(a.count(u.se)) continue;
          nab.insert(u);
        }
        if(nab.size()==0) break;
        int ne=nab.begin()->se;
        vis[ne]=true;
        //cout <<ne<<endl;
        nab.erase(*nab.begin());
        a.insert(ne);
        adj[ne].pb(b);
        adj[b].pb(ne);
        b=ne;
      }
      
    }
    state[mx.se]=true;
    dfs(mx.se,-1);
    ans(mx.se,-1);
    for (int i = 0; i < n; ++i)
    {
      cout <<res[i];
    }
}

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