Submission #993748

#	Time	Username	Problem	Language	Result	Execution time	Memory
993748		MarwenElarbi	Stranded Far From Home (BOI22_island)	C++17	10 / 100	210 ms	45904 KiB

island

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
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];
}
void build(int x){
  vis[x]=true;
  for(auto u:adj[x]){
    if(vis[u]) continue;
    newadj[x].pb(u);
    newadj[u].pb(x);
    build(u);
  }
  return;
}
void dfs(int x,int p){
  sz[x]=tab[x];
  //cout <<x<<" "<<p<<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