oj.uz

Submission #599751

# Submission time Handle Problem Language Result Execution time Memory
599751 2022-07-19T20:11:11 Z Mounir Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 74272 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);
      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 11 ms 21416 KB Output is correct
3 Correct 10 ms 21484 KB Output is correct
4 Correct 19 ms 21744 KB Output is correct
5 Correct 13 ms 21836 KB Output is correct
6 Correct 12 ms 21716 KB Output is correct
7 Correct 17 ms 21732 KB Output is correct
8 Correct 18 ms 21716 KB Output is correct
9 Correct 32 ms 21972 KB Output is correct
10 Correct 13 ms 21856 KB Output is correct
11 Correct 13 ms 21824 KB Output is correct
12 Correct 12 ms 21904 KB Output is correct
13 Correct 29 ms 21840 KB Output is correct
14 Correct 17 ms 21844 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 10 ms 21460 KB Output is correct
3 Execution timed out 1094 ms 37668 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21460 KB Output is correct
2 Correct 378 ms 73968 KB Output is correct
3 Correct 376 ms 74272 KB Output is correct
4 Execution timed out 1100 ms 36576 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 21460 KB Output is correct
2 Correct 385 ms 62624 KB Output is correct
3 Correct 396 ms 66596 KB Output is correct
4 Correct 448 ms 68372 KB Output is correct
5 Correct 361 ms 67156 KB Output is correct
6 Correct 323 ms 64340 KB Output is correct
7 Correct 180 ms 44760 KB Output is correct
8 Execution timed out 1098 ms 38232 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 11 ms 21416 KB Output is correct
3 Correct 10 ms 21484 KB Output is correct
4 Correct 19 ms 21744 KB Output is correct
5 Correct 13 ms 21836 KB Output is correct
6 Correct 12 ms 21716 KB Output is correct
7 Correct 17 ms 21732 KB Output is correct
8 Correct 18 ms 21716 KB Output is correct
9 Correct 32 ms 21972 KB Output is correct
10 Correct 13 ms 21856 KB Output is correct
11 Correct 13 ms 21824 KB Output is correct
12 Correct 12 ms 21904 KB Output is correct
13 Correct 29 ms 21840 KB Output is correct
14 Correct 17 ms 21844 KB Output is correct
15 Correct 12 ms 21460 KB Output is correct
16 Correct 10 ms 21460 KB Output is correct
17 Execution timed out 1094 ms 37668 KB Time limit exceeded
18 Halted 0 ms 0 KB -