oj.uz

Submission #1104577

# Submission time Handle Problem Language Result Execution time Memory
1104577 2024-10-24T04:44:16 Z Nxmkxing Tropical Garden (IOI11_garden) C++14
100 / 100
 1524 ms 50868 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, 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.0 / 49.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21328 KB Output is correct
2 Correct 5 ms 21072 KB Output is correct
3 Correct 5 ms 21072 KB Output is correct
4 Correct 5 ms 21072 KB Output is correct
5 Correct 4 ms 21072 KB Output is correct
6 Correct 4 ms 21328 KB Output is correct
7 Correct 4 ms 21072 KB Output is correct
8 Correct 4 ms 21072 KB Output is correct
9 Correct 6 ms 21328 KB Output is correct
10 Correct 4 ms 21240 KB Output is correct
11 Correct 11 ms 24912 KB Output is correct
12 Correct 22 ms 26192 KB Output is correct
13 Correct 60 ms 44372 KB Output is correct
14 Correct 70 ms 32644 KB Output is correct
15 Correct 82 ms 33096 KB Output is correct
16 Correct 70 ms 30792 KB Output is correct
17 Correct 53 ms 30024 KB Output is correct
18 Correct 23 ms 26360 KB Output is correct
19 Correct 71 ms 32840 KB Output is correct
20 Correct 117 ms 32900 KB Output is correct
21 Correct 56 ms 30792 KB Output is correct
22 Correct 51 ms 30040 KB Output is correct
23 Correct 78 ms 33612 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21328 KB Output is correct
2 Correct 5 ms 21072 KB Output is correct
3 Correct 5 ms 21072 KB Output is correct
4 Correct 5 ms 21072 KB Output is correct
5 Correct 4 ms 21072 KB Output is correct
6 Correct 4 ms 21328 KB Output is correct
7 Correct 4 ms 21072 KB Output is correct
8 Correct 4 ms 21072 KB Output is correct
9 Correct 6 ms 21328 KB Output is correct
10 Correct 4 ms 21240 KB Output is correct
11 Correct 11 ms 24912 KB Output is correct
12 Correct 22 ms 26192 KB Output is correct
13 Correct 60 ms 44372 KB Output is correct
14 Correct 70 ms 32644 KB Output is correct
15 Correct 82 ms 33096 KB Output is correct
16 Correct 70 ms 30792 KB Output is correct
17 Correct 53 ms 30024 KB Output is correct
18 Correct 23 ms 26360 KB Output is correct
19 Correct 71 ms 32840 KB Output is correct
20 Correct 117 ms 32900 KB Output is correct
21 Correct 56 ms 30792 KB Output is correct
22 Correct 51 ms 30040 KB Output is correct
23 Correct 78 ms 33612 KB Output is correct
24 Correct 4 ms 21072 KB Output is correct
25 Correct 100 ms 24912 KB Output is correct
26 Correct 205 ms 26184 KB Output is correct
27 Correct 713 ms 45440 KB Output is correct
28 Correct 879 ms 34568 KB Output is correct
29 Correct 750 ms 34632 KB Output is correct
30 Correct 469 ms 32584 KB Output is correct
31 Correct 456 ms 31820 KB Output is correct
32 Correct 170 ms 26704 KB Output is correct
33 Correct 929 ms 34568 KB Output is correct
34 Correct 722 ms 34860 KB Output is correct
35 Correct 504 ms 32328 KB Output is correct
36 Correct 873 ms 31620 KB Output is correct
37 Correct 784 ms 35644 KB Output is correct
38 Correct 1524 ms 50868 KB Output is correct