Submission #599753

#	Time	Username	Problem	Language	Result	Execution time	Memory
599753		Mounir	Stranded Far From Home (BOI22_island)	C++14	100 / 100	305 ms	65840 KiB

island

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define chmax(x, v) x = max(x, v)
#define chmin(x, v) x = min(x, v)
#define pb push_back
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define x first
#define y second
#define int long long
using namespace std;
 
const int N = 3e5;
int sousArbre[N];
vector<int> enfants[N];
vector<int> winner[N];
int vals[N];
 
void dfs(int noeud){
      sousArbre[noeud] = vals[noeud];
      for (int enfant : enfants[noeud]){
            dfs(enfant);
            sousArbre[noeud] += sousArbre[enfant];
            if (sousArbre[enfant] >= vals[noeud])
                  winner[noeud].pb(enfant);
      }
}
 
bool vainqueur[N];
void complete(int noeud){
      vainqueur[noeud] = true;
      for (int enf : winner[noeud])
            complete(enf);
}
 
struct Noeud {
      int noeud, val;
 
      bool operator < (const Noeud &autre) const {
            if (val != autre.val)
                  return val < autre.val;
            return noeud < autre.noeud;
      }
};
 
vector<int> voisins[N];
int ens[N];
int getEns(int noeud){
      if (ens[noeud] != noeud)
            ens[noeud] = getEns(ens[noeud]);
      return ens[noeud];
}
 
 
signed main(){ 
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      int nNoeuds, nAretes; cin >> nNoeuds >> nAretes;
      for (int noeud = 0; noeud < nNoeuds; ++noeud)
            ens[noeud] = noeud;
      for (int i = 0; i < nNoeuds; ++i)
            cin >> vals[i];
      for (int i = 0; i < nAretes; ++i){
            int u, v; cin >> u >> v;
            u--; v--;
            voisins[u].pb(v);
            voisins[v].pb(u);
      }
 
      vector<Noeud> sac;
      for (int noeud = 0; noeud < nNoeuds; ++noeud)
            sac.pb({noeud, vals[noeud]});
      sort(all(sac));
      int root = -1;    
      for (Noeud nod : sac){
            int noeud = nod.noeud;
            for (int& voisin : voisins[noeud]){
                  voisin = getEns(voisin);
                  if ((vals[noeud] > vals[voisin]) || (vals[noeud] == vals[voisin] && voisin < noeud)){
                        ens[voisin] = noeud;
                        enfants[noeud].pb(voisin);
                  }
            }
            root = noeud;
      }
/*
      for (int noeud = 0; noeud < nNoeuds; ++noeud){
            cout << "Noeud " << noeud << endl;
            for (int enf : enfants[noeud])
                  cout << enf << " ";
            cout << endl;
      }*/

      dfs(root);
      complete(root);
      for(int i = 0; i < nNoeuds; ++i)
            cout << vainqueur[i];
      cout << endl;
      return 0;   
}

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