oj.uz

Submission #599742

# Submission time Handle Problem Language Result Execution time Memory
599742 2022-07-19T20:05:28 Z Mounir Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 74296 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(){ 
      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;
            for (int& voisin : voisins[containerVoisins[noeud]]){
                  voisin = getEns(voisin);
                  if (voisin == noeud) continue;
                  if (vals[voisin] >= vals[noeud] && (pere == -1 || vals[pere] > vals[voisin]))
                        pere = voisin;
            }

            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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21460 KB Output is correct
2 Correct 12 ms 21416 KB Output is correct
3 Correct 11 ms 21464 KB Output is correct
4 Correct 23 ms 21732 KB Output is correct
5 Correct 18 ms 21824 KB Output is correct
6 Correct 14 ms 21716 KB Output is correct
7 Correct 22 ms 21748 KB Output is correct
8 Correct 20 ms 21716 KB Output is correct
9 Correct 31 ms 21908 KB Output is correct
10 Correct 14 ms 21844 KB Output is correct
11 Correct 13 ms 21856 KB Output is correct
12 Correct 14 ms 21980 KB Output is correct
13 Correct 29 ms 21836 KB Output is correct
14 Correct 14 ms 21844 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21460 KB Output is correct
2 Correct 11 ms 21460 KB Output is correct
3 Execution timed out 1071 ms 37988 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 21460 KB Output is correct
2 Correct 545 ms 74012 KB Output is correct
3 Correct 539 ms 74296 KB Output is correct
4 Execution timed out 1085 ms 36668 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21460 KB Output is correct
2 Correct 571 ms 62936 KB Output is correct
3 Correct 525 ms 66784 KB Output is correct
4 Correct 588 ms 68256 KB Output is correct
5 Correct 531 ms 67352 KB Output is correct
6 Correct 465 ms 64316 KB Output is correct
7 Correct 293 ms 44796 KB Output is correct
8 Execution timed out 1089 ms 38244 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21460 KB Output is correct
2 Correct 12 ms 21416 KB Output is correct
3 Correct 11 ms 21464 KB Output is correct
4 Correct 23 ms 21732 KB Output is correct
5 Correct 18 ms 21824 KB Output is correct
6 Correct 14 ms 21716 KB Output is correct
7 Correct 22 ms 21748 KB Output is correct
8 Correct 20 ms 21716 KB Output is correct
9 Correct 31 ms 21908 KB Output is correct
10 Correct 14 ms 21844 KB Output is correct
11 Correct 13 ms 21856 KB Output is correct
12 Correct 14 ms 21980 KB Output is correct
13 Correct 29 ms 21836 KB Output is correct
14 Correct 14 ms 21844 KB Output is correct
15 Correct 13 ms 21460 KB Output is correct
16 Correct 11 ms 21460 KB Output is correct
17 Execution timed out 1071 ms 37988 KB Time limit exceeded
18 Halted 0 ms 0 KB -