oj.uz

Submission #1104568

# Submission time Handle Problem Language Result Execution time Memory
1104568 2024-10-24T04:12:59 Z Nxmkxing Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 55372 KB 
#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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12880 KB Output is correct
2 Correct 3 ms 12880 KB Output is correct
3 Correct 3 ms 12880 KB Output is correct
4 Correct 2 ms 13076 KB Output is correct
5 Correct 2 ms 12880 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 3 ms 12880 KB Output is correct
8 Correct 3 ms 12880 KB Output is correct
9 Correct 4 ms 13136 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12880 KB Output is correct
2 Correct 3 ms 12880 KB Output is correct
3 Correct 3 ms 12880 KB Output is correct
4 Correct 2 ms 13076 KB Output is correct
5 Correct 2 ms 12880 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 3 ms 12880 KB Output is correct
8 Correct 3 ms 12880 KB Output is correct
9 Correct 4 ms 13136 KB Output is correct
10 Correct 3 ms 12880 KB Output is correct
11 Correct 14 ms 19804 KB Output is correct
12 Correct 28 ms 25032 KB Output is correct
13 Correct 46 ms 38152 KB Output is correct
14 Correct 77 ms 54028 KB Output is correct
15 Correct 81 ms 55112 KB Output is correct
16 Correct 70 ms 43080 KB Output is correct
17 Correct 53 ms 37960 KB Output is correct
18 Correct 26 ms 24912 KB Output is correct
19 Correct 87 ms 54100 KB Output is correct
20 Correct 85 ms 55072 KB Output is correct
21 Correct 59 ms 42112 KB Output is correct
22 Correct 52 ms 38736 KB Output is correct
23 Correct 102 ms 55372 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12880 KB Output is correct
2 Correct 3 ms 12880 KB Output is correct
3 Correct 3 ms 12880 KB Output is correct
4 Correct 2 ms 13076 KB Output is correct
5 Correct 2 ms 12880 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 3 ms 12880 KB Output is correct
8 Correct 3 ms 12880 KB Output is correct
9 Correct 4 ms 13136 KB Output is correct
10 Correct 3 ms 12880 KB Output is correct
11 Correct 14 ms 19804 KB Output is correct
12 Correct 28 ms 25032 KB Output is correct
13 Correct 46 ms 38152 KB Output is correct
14 Correct 77 ms 54028 KB Output is correct
15 Correct 81 ms 55112 KB Output is correct
16 Correct 70 ms 43080 KB Output is correct
17 Correct 53 ms 37960 KB Output is correct
18 Correct 26 ms 24912 KB Output is correct
19 Correct 87 ms 54100 KB Output is correct
20 Correct 85 ms 55072 KB Output is correct
21 Correct 59 ms 42112 KB Output is correct
22 Correct 52 ms 38736 KB Output is correct
23 Correct 102 ms 55372 KB Output is correct
24 Correct 10 ms 12880 KB Output is correct
25 Correct 2855 ms 20136 KB Output is correct
26 Execution timed out 5052 ms 25424 KB Time limit exceeded
27 Halted 0 ms 0 KB -