Submission #592700

#	Time	Username	Problem	Language	Result	Execution time	Memory
592700		Mamedov	Tropical Garden (IOI11_garden)	C++17	100 / 100	2615 ms	27692 KiB

garden

#pragma GCC optimize ("O3")
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void dfs(int node, vvi &g, vi &dist, int &cycle) {
  for (int to : g[node]) {
    if (dist[to] == oo) {
      dist[to] = dist[node] + 1;
      dfs(to, g, dist, cycle);
    } else {
      cycle = dist[node] + 1;
    }
  }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  vvi minTrail(2, vi(N, -1));
  for (int i = 0; i < M; ++i) {
    for (int j = 0; j < 2; ++j) {
      int u = R[i][j];
      if (minTrail[0][u] == -1) {
        minTrail[0][u] = i;
      } else if (minTrail[1][u] == -1) {
        minTrail[1][u] = i;
      }
    }
  }
  for (int i = 0; i < N; ++i) {
    if (minTrail[1][i] == -1) {
      minTrail[1][i] = minTrail[0][i];
    }
  }

  vvi gt(2 * N);
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 2; ++j) {
      int trail = minTrail[j][i];
      int node = R[trail][0] + R[trail][1] - i;
      if (minTrail[0][node] == trail) {
        node += N;
      }
      gt[node].eb(i + j * N);
    }
  }
  vi cycle(2, 0);
  vvi dist(2, vi(2 * N, oo));
  dist[0][P] = 0;
  dfs(P, gt, dist[0], cycle[0]);
  dist[1][P + N] = 0;
  dfs(P + N, gt, dist[1], cycle[1]);
  for (int i = 0; i < Q; ++i) {
    int cnt = 0;
    for (int j = 0; j < N; ++j) {
      if (dist[0][j] == G[i] || (cycle[0] && G[i] > dist[0][j] && (G[i] - dist[0][j]) % cycle[0] == 0)) {
        ++cnt;
      } else if (dist[1][j] == G[i] || (cycle[1] && G[i] > dist[1][j] && (G[i] - dist[1][j]) % cycle[1] == 0)) {
        ++cnt;
      }
    }
    answer(cnt);
  }
}

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