Submission #1104557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104557		Nxmkxing	Tropical Garden (IOI11_garden)	C++14	69 / 100	5081 ms	92128 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 = 2e5 + 10;
const int MxL = 32;
int n, m, p, q, ans[MxN], g[MxN];
pii up[MxN][MxL][2];
vector<pii> adj[MxN];

int cnt = -1;

pii dfs(int u, int l, int op) {
  if (l == 0) {
    return up[u][l][op] = pii(adj[u][op].second, u);
  }
  if (up[u][l][op] != pii(-1, -1)) return up[u][l][op];
  pii cur = pii(u, -1);
  cur = dfs(cur.first, l - 1, op);
  int new_op = 0;
  if (cur.second == adj[cur.first][0].second) new_op = 1;
  cur = dfs(cur.first, l - 1, new_op);
  return up[u][l][op] = cur;
}

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());
    if (adj[i].size() == 1) adj[i].push_back({-1, adj[i][0].second});
    adj[i].resize(2);
  }
  for (int j = 0; j < MxL; j++) {
    for (int i = 0; i < n; i++) {
      up[i][j][0] = up[i][j][1] = pii(-1, -1);
      dfs(i, j, 0); dfs(i, j, 1);
    }
  }
  for (int i = 0; i < q; i++) {
    int ans = 0;
    for (int j = 0; j < n; j++) {
      pii cur = pii(j, -1);
      int op = 0;
      for (int k = 0; k < MxL; k++) {
        if (g[i] & (1 << k)) {
          cur = up[cur.first][k][op];
          if (cur.second == adj[cur.first][0].second) op = 1;
          else op = 0;
        }
      }
      if (cur.first == p) ans++;
    }
    answer(ans);
  }
}

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