Submission #993753

#	Time	Username	Problem	Language	Result	Execution time	Memory
993753		MarwenElarbi	Stranded Far From Home (BOI22_island)	C++17	10 / 100	494 ms	46020 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];
bool vis[nax];
int tab[nax];
bool state[nax];
long long sz[nax];
int res[nax];
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 build(int x){
  vis[x]=true;
  priority_queue<node,vector<node>,compare2> pq;
  for(auto u:adj[x]){
    pq.push({tab[u],tab[x],u,x});
  }
  while(!pq.empty()){
    auto cur=pq.top();
    pq.pop();
    if(vis[cur.x]) continue;
    //cout <<cur.x<<" "<<cur.p<<endl;
    newadj[cur.x].pb(cur.p);
    newadj[cur.p].pb(cur.x);
    vis[cur.x]=true;
    for(auto u:adj[cur.x]){
      pq.push({tab[u],tab[cur.x],u,cur.x});
    }
  }
}
void dfs(int x,int p){
  sz[x]=tab[x];
  //cout <<newadj[x].size()<<" "<<x<<endl;
  for(auto u:newadj[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:newadj[x]){
    if(u==p) continue;
    ans(u,x);
  }
}
int main() {
    int n,m;
    cin>>n>>m;
    pair<int,int> mx={-1,-1};
    for (int i = 0; i < n; ++i)
    {
        cin>>tab[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]){
        adj[x].pb(y);
        adj[y].pb(x);
      }else if(tab[x]>tab[y]){
        adj[x].pb(y);
      }else{
        adj[y].pb(x);
      }
    }
    for (int i = 0; i < n; ++i)
    {
      sort(adj[i].begin(),adj[i].end(),compare);
    }
    build(mx.se);
    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: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35