Submission #363383

#	Time	Username	Problem	Language	Result	Execution time	Memory
363383		WLZ	Tropical Garden (IOI11_garden)	C++14	100 / 100	3016 ms	43504 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int bfs(int s, const vector< vector<int> > &g, vector<int> &dist) {
  int n = (int) g.size();
  dist.assign(n, -1); dist[s] = 0;
  queue<int> q; q.push(s);
  int c = -1;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (auto& v : g[u]) {
      if (dist[v] == -1) {
        dist[v] = dist[u] + 1;
        q.push(v);
      }
      if (v == s) {
        c = dist[u] + 1;
      }
    }
  }
  return c;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  vector< set<int> > mn(N);
  for (int i = 0; i < M; i++) {
    mn[R[i][0]].insert(i);
    mn[R[i][1]].insert(i);
  }
  vector< vector<int> > g(2 * N);
  for (int i = 0; i < N; i++) {
    int idx = *mn[i].begin();
    int other = R[idx][0];
    if (other == i) other = R[idx][1];
    if (idx == *mn[other].begin() && (int) mn[other].size() > 1) g[2 * other + 1].push_back(2 * i);
    else g[2 * other].push_back(2 * i);
    if ((int) mn[i].size() == 1) continue;
    idx = *next(mn[i].begin());
    other = R[idx][0];
    if (other == i) other = R[idx][1];
    if (idx == *mn[other].begin() && (int) mn[other].size() > 1) g[2 * other + 1].push_back(2 * i + 1);
    else g[2 * other].push_back(2 * i + 1);
  }
  vector<int> dist1, dist2;
  int c1 = bfs(2 * P, g, dist1);
  int c2 = bfs(2 * P + 1, g, dist2);
  for (int i = 0; i < Q; i++) {
    int cnt = 0;
    for (int u = 0; u < 2 * N; u += 2) {
      bool b1 = dist1[u] != -1;
      if (c1 == -1) b1 = b1 && dist1[u] == G[i];
      else b1 = b1 && dist1[u] <= G[i] && (G[i] - dist1[u]) % c1 == 0;
      bool b2 = dist2[u] != -1;
      if (c2 == -1) b2 = b2 && dist2[u] == G[i];
      else b2 = b2 && dist2[u] <= G[i] && (G[i] - dist2[u]) % c2 == 0;
      if (b1 || b2) cnt++;
    }
    answer(cnt);
  }
}

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