oj.uz

Submission #599747

# Submission time Handle Problem Language Result Execution time Memory
599747 2022-07-19T20:07:52 Z Mounir Stranded Far From Home (BOI22_island) C++14
0 / 100
 333 ms 46036 KB 
#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], containerVoisins[N];
int getEns(int noeud){
      if (ens[noeud] != noeud)
            ens[noeud] = getEns(ens[noeud]);
      return ens[noeud];
}

int fusion(int a, int b){
      if (sz(voisins[a]) < sz(voisins[b]))
            return fusion(b, a);
      
      for (int voisin : voisins[b])
            voisins[a].pb(voisin);
      return a;
}

signed main(){ 
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);
      int nNoeuds, nAretes; cin >> nNoeuds >> nAretes;
      for (int noeud = 0; noeud < nNoeuds; ++noeud)
            ens[noeud] = containerVoisins[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;
            int pere = -1;
            vector<int> vrais;
            for (int& voisin : voisins[containerVoisins[noeud]]){
                  voisin = getEns(voisin);
                  if (voisin == noeud) continue;
                  if (vals[voisin] >= vals[noeud]){
                        vrais.pb(voisin);
                        if (pere == -1 || vals[pere] > vals[voisin])
                              pere = voisin;
                  }
            }

            voisins[containerVoisins[noeud]] = vrais;

            if (pere == -1) {
                  root = noeud;
                  continue;
            }
            enfants[pere].pb(noeud);
            ens[noeud] = pere;
            containerVoisins[pere] = fusion(containerVoisins[pere], containerVoisins[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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21460 KB Output is correct
2 Correct 10 ms 21492 KB Output is correct
3 Correct 10 ms 21472 KB Output is correct
4 Incorrect 13 ms 21588 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21460 KB Output is correct
2 Correct 10 ms 21440 KB Output is correct
3 Incorrect 180 ms 46036 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21460 KB Output is correct
2 Incorrect 296 ms 39528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21460 KB Output is correct
2 Incorrect 333 ms 39032 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21460 KB Output is correct
2 Correct 10 ms 21492 KB Output is correct
3 Correct 10 ms 21472 KB Output is correct
4 Incorrect 13 ms 21588 KB Output isn't correct
5 Halted 0 ms 0 KB -