Submission #1104577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104577		Nxmkxing	Tropical Garden (IOI11_garden)	C++14	100 / 100	1524 ms	50868 KiB

garden

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

using ll = long long;
using pii = pair<int, int>;
const int inf = 1e9;

const int MxN = 3e5 + 10;
const int MxL = 32;
int n, m, p, q, g[MxN], vis[MxN][2], dis[MxN][2], cyc[2], up[MxN][MxL];
vector<pii> adj[MxN];
vector<int> radj[MxN];

int neg(int u) {
  return u < n ? u + n : u - n;
}

int is_neg(int u, int p) {
  if (adj[u][0].second == p) return neg(u);
  else return u;
}

void dfs(int u, int st, int i) {
  vis[u][i] = true;
  for (int v : radj[u]) {
    if (v == st && vis[v][i]) cyc[i] = dis[u][i] + 1;
    if (!vis[v][i]) {
      dis[v][i] = dis[u][i] + 1;
      dfs(v, st, i);
    }
  }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  n = N, m = M, p = P;
  for (int i = 0; i < M; i++) {
    int u = R[i][0];
    int v = R[i][1];
    adj[u].push_back({i, v});
    adj[v].push_back({i, u});
  }
  q = Q;
  for (int i = 0; i < Q; i++) {
    g[i] = G[i];
  }
  for (int i = 0; i < n; i++) {
    sort(adj[i].begin(), adj[i].end());
  }
  for (int i = 0; i < n; i++) {
    radj[is_neg(adj[i][0].second, i)].push_back(i);
    radj[adj[i].size() < 2 ? is_neg(adj[i][0].second, i) : is_neg(adj[i][1].second, i)].push_back(neg(i));
  }
  memset(dis, -1, sizeof dis);
  dis[p][0] = 0, dis[neg(p)][1] = 0;
  dfs(p, p, 0);
  dfs(neg(p), neg(p), 1);
  for (int i = 0; i < q; i++) {
    int ans = 0;
    for (int j = 0; j < n; j++) {
      int ok = 0;
      for (int k = 0; k < 2; k++) {
        if (dis[j][k] == -1) continue;
        int len = g[i] - dis[j][k];
        if (len < 0) continue;
        if (cyc[k] == 0 && len == 0) ok = 1;
        else if (cyc[k] != 0 && len % cyc[k] == 0) ok = 1;
      }
      ans += ok;
    }
    answer(ans);
  }
}

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