oj.uz

Submission #599731

# Submission time Handle Problem Language Result Execution time Memory
599731 2022-07-19T19:50:59 Z Mounir Stranded Far From Home (BOI22_island) C++14
10 / 100
 263 ms 46100 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);
}

signed main(){ 
      int nNoeuds, nAretes; cin >> nNoeuds >> nAretes;
      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--;
            if (u > v)
                  swap(u, v);
            enfants[u].pb(v);
      }
      dfs(0);
      complete(0);
      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 7 ms 14384 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Incorrect 8 ms 14432 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 237 ms 32108 KB Output is correct
4 Correct 202 ms 32972 KB Output is correct
5 Correct 236 ms 24552 KB Output is correct
6 Correct 245 ms 24864 KB Output is correct
7 Correct 246 ms 24996 KB Output is correct
8 Correct 263 ms 26372 KB Output is correct
9 Correct 212 ms 22264 KB Output is correct
10 Correct 165 ms 19384 KB Output is correct
11 Correct 165 ms 22108 KB Output is correct
12 Correct 210 ms 26104 KB Output is correct
13 Correct 199 ms 45920 KB Output is correct
14 Correct 204 ms 45900 KB Output is correct
15 Correct 240 ms 46100 KB Output is correct
16 Correct 197 ms 45732 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14412 KB Output is correct
2 Incorrect 237 ms 45836 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 213 ms 20300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14384 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Incorrect 8 ms 14432 KB Output isn't correct
5 Halted 0 ms 0 KB -