Submission #1104568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104568		Nxmkxing	Tropical Garden (IOI11_garden)	C++14	69 / 100	5052 ms	55372 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, ans[MxN], g[MxN], up[MxN][MxL];
vector<pii> adj[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 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++) {
    up[i][0] = is_neg(adj[i][0].second, i);
    up[neg(i)][0] = adj[i].size() < 2 ? is_neg(adj[i][0].second, i) : is_neg(adj[i][1].second, i);
  }
  for (int j = 1; j < MxL; j++) {
    for (int i = 0; i < 2 * n; i++) {
      up[i][j] = up[up[i][j-1]][j-1];
    }
  }
  for (int i = 0; i < q; i++) {
    int ans = 0;
    for (int j = 0; j < n; j++) {
      int cur = j;
      for (int k = 0; k < MxL; k++) {
        if (g[i] & (1 << k)) {
          cur = up[cur][k];
        }
      }
      if (cur == p || cur == neg(p)) ans++;
    }
    answer(ans);
  }
}

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