Submission #37189

#	Time	Username	Problem	Language	Result	Execution time	Memory
37189		szawinis	Tropical Garden (IOI11_garden)	C++14	100 / 100	3871 ms	35920 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <tuple>
using namespace std;
const int N = 3e5 + 1, INF = 1e9+1;

int n, p, q, res[N], d[N];
vector<int> g[N], cycle;
vector<pair<int, int>> init_g[N];

int cycle_size;
bool mark[N];
void dfs(int u) {
  mark[u] = true;
  for(int v: g[u]) {
    if(!mark[v]) {
      d[v] = d[u] + 1;
      dfs(v);
    } else if(v == p) cycle_size = d[u] + 1;
  }
}

void calc() {
  fill(mark, mark+2*n, 0);
  fill(d, d+2*n, 0);
  cycle_size = 0;
  dfs(p);
}

int solve(int len) {
  int ret = 0;
  if(cycle_size) {
    for(int i = 0; i < n; i++) if(mark[i])
      ret += d[i] <= len && (len - d[i]) % cycle_size == 0;
  } else {
    for(int i = 0; i < n; i++) if(mark[i])
      ret += d[i] == len;
  }
  return ret;
}

void count_routes(int _n, int m, int _p, int _e[][2], int _q, int len[]) {
  n = _n, p = _p, q = _q;
  for(int i = 0; i < m; i++) {
    if(init_g[_e[i][0]].size() < 2)
      init_g[_e[i][0]].emplace_back(_e[i][1], i);
    if(init_g[_e[i][1]].size() < 2)
      init_g[_e[i][1]].emplace_back(_e[i][0], i);
  }
  for(int i = 0; i < n; i++) if(init_g[i].size() == 1) init_g[i].push_back(init_g[i][0]);
  for(int u = 0; u < n; u++) {
    for(int i = 0, v, idx; i < min((int)init_g[u].size(), 2); i++) {
      tie(v, idx) = init_g[u][i];
      g[v + (idx == init_g[v][0].second) * n].push_back(u + i * n);
    }
  }
  calc();
  for(int i = 0; i < q; i++) res[i] += solve(len[i]);
  p += n;
  calc();
  for(int i = 0; i < q; i++) res[i] += solve(len[i]);
  for(int i = 0; i < q; i++) answer(res[i]);
}

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31