oj.uz

Submission #390513

# Submission time Handle Problem Language Result Execution time Memory
390513 2021-04-16T08:59:08 Z AlexPop28 Comparing Plants (IOI20_plants) C++11
0 / 100
 1 ms 204 KB 
#include "plants.h"
#include <cassert>
#include <iostream>
// regret ca mi a fost lene sa scriu 2 linii de define uri si am stat sa scriu printf uri ca prostu

using namespace std;

vector<int> h, topo;
vector<bool> visited;
vector<vector<int>> adj;

void DFS(int node) {
  if (visited[node]) return;
  visited[node] = true;
  for (int x : adj[node]) DFS(x);
  topo.emplace_back(node);
}

void init(int k_, vector<int> r) {
  int n = r.size();
  h.resize(n);
  topo.resize(n);
  visited.resize(n);
  adj.resize(n);

  vector<int> in(n);
  for (int i = 0; i < n; ++i) {
    int j = (i + 1) % n;
    if (r[i] == 0) {
      adj[i].emplace_back(j);
      ++in[j];
    } else {
      adj[j].emplace_back(i);
      ++in[i];
    }
  }

  for (int i = 0; i < n; ++i) {
    if (in[i] == 0) {
      DFS(i);
    }
  }

  for (int node : topo) {
    for (int x : adj[node]) {
      h[node] = max(h[node], h[x] + 1);
    }
  }
}

int compare_plants(int x, int y) {
  if (h[x] == h[y]) return 0;
  return 2 * (h[x] > h[y]) - 1;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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