Submission #390513

#	Time	Username	Problem	Language	Result	Execution time	Memory
390513		AlexPop28	Comparing Plants (IOI20_plants)	C++11	0 / 100	1 ms	204 KiB

plants

#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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25