oj.uz

Submission #1113097

# Submission time Handle Problem Language Result Execution time Memory
1113097 2024-11-15T17:32:52 Z ortsac Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 85932 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define fr first
#define se second

struct Edge {
  int idx, to;

  Edge(int a = 0, int b = 0) : idx(a), to(b) {}

  bool operator < (const Edge& a) const {
    return (idx < a.idx);
  }
};

const int MAXN = 150010;
const int INF = 0x3f3f3f3f;
const int MAXLOG = 30;
int n, m, p;

vector<Edge> adj[MAXN];
pii nxt[MAXN][2];
pii binl[30][MAXN][2];
int mi[MAXN];

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 < n; i++) {
    mi[i] = INF;
  }
  for (int i = 0; i < m; i++) {
    int a = R[i][0], b = R[i][1];
    adj[a].push_back(Edge(i, b));
    adj[b].push_back(Edge(i, a));
    mi[a] = min(mi[a], i);
    mi[b] = min(mi[b], i);
  }
  for (int i = 0; i < n; i++) {
    sort(adj[i].begin(), adj[i].end());
  }
  for (int i = 0; i < n; i++) {
    // faz o do 0
    bool f = 0;
    if (mi[adj[i][0].to] == adj[i][0].idx) f = 1;
    nxt[i][0] = make_pair(adj[i][0].to, f);
    // faz o do 1
    if (((int) adj[i].size()) == 1) {
      nxt[i][1] = nxt[i][0];
    } else {
      f = 0;
      if (mi[adj[i][1].to] == adj[i][1].idx) f = 1;
      nxt[i][1] = make_pair(adj[i][1].to, f);
    }
  }
  // calcular bin lift
  for (int i = 0; i < n; i++) {
    binl[0][i][0] = nxt[i][0];
    binl[0][i][1] = nxt[i][1];
  }
  for (int k = 1; k < MAXLOG; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 2; j++) {
        pii a = binl[k - 1][i][j];
        binl[k][i][j] = binl[k - 1][a.fr][a.se];
      }
    }
  }
  for (int q = 0; q < Q; q++) {
    int k = G[q];
    int ans = 0;
    for (int i = 0; i < n; i++) {
      pii curr = {i, 0};
      for (int b = 0; b < MAXLOG; b++) {
        if (k & (1 << b)) curr = binl[b][curr.fr][curr.se];
      }
      if (curr.fr == p) ans++;
    }
    answer(ans);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 70224 KB Output is correct
2 Correct 6 ms 62032 KB Output is correct
3 Correct 7 ms 62032 KB Output is correct
4 Correct 7 ms 62032 KB Output is correct
5 Correct 7 ms 69968 KB Output is correct
6 Correct 7 ms 62080 KB Output is correct
7 Correct 6 ms 62164 KB Output is correct
8 Correct 6 ms 57936 KB Output is correct
9 Correct 8 ms 58288 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 70224 KB Output is correct
2 Correct 6 ms 62032 KB Output is correct
3 Correct 7 ms 62032 KB Output is correct
4 Correct 7 ms 62032 KB Output is correct
5 Correct 7 ms 69968 KB Output is correct
6 Correct 7 ms 62080 KB Output is correct
7 Correct 6 ms 62164 KB Output is correct
8 Correct 6 ms 57936 KB Output is correct
9 Correct 8 ms 58288 KB Output is correct
10 Correct 6 ms 54008 KB Output is correct
11 Correct 15 ms 47952 KB Output is correct
12 Correct 26 ms 56316 KB Output is correct
13 Correct 39 ms 65072 KB Output is correct
14 Correct 72 ms 82248 KB Output is correct
15 Correct 77 ms 82760 KB Output is correct
16 Correct 70 ms 64840 KB Output is correct
17 Correct 66 ms 58952 KB Output is correct
18 Correct 26 ms 46928 KB Output is correct
19 Correct 90 ms 80816 KB Output is correct
20 Correct 82 ms 81992 KB Output is correct
21 Correct 60 ms 68980 KB Output is correct
22 Correct 49 ms 78408 KB Output is correct
23 Correct 90 ms 85932 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 70224 KB Output is correct
2 Correct 6 ms 62032 KB Output is correct
3 Correct 7 ms 62032 KB Output is correct
4 Correct 7 ms 62032 KB Output is correct
5 Correct 7 ms 69968 KB Output is correct
6 Correct 7 ms 62080 KB Output is correct
7 Correct 6 ms 62164 KB Output is correct
8 Correct 6 ms 57936 KB Output is correct
9 Correct 8 ms 58288 KB Output is correct
10 Correct 6 ms 54008 KB Output is correct
11 Correct 15 ms 47952 KB Output is correct
12 Correct 26 ms 56316 KB Output is correct
13 Correct 39 ms 65072 KB Output is correct
14 Correct 72 ms 82248 KB Output is correct
15 Correct 77 ms 82760 KB Output is correct
16 Correct 70 ms 64840 KB Output is correct
17 Correct 66 ms 58952 KB Output is correct
18 Correct 26 ms 46928 KB Output is correct
19 Correct 90 ms 80816 KB Output is correct
20 Correct 82 ms 81992 KB Output is correct
21 Correct 60 ms 68980 KB Output is correct
22 Correct 49 ms 78408 KB Output is correct
23 Correct 90 ms 85932 KB Output is correct
24 Correct 9 ms 35408 KB Output is correct
25 Correct 2403 ms 41272 KB Output is correct
26 Execution timed out 5057 ms 53328 KB Time limit exceeded
27 Halted 0 ms 0 KB -