oj.uz

Submission #1036931

# Submission time Handle Problem Language Result Execution time Memory
1036931 2024-07-27T19:57:37 Z aaaaaarroz Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 84560 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150000;
const int MAXLOG = 30;
const int MAXM = 150000;
pair<int,int> f[MAXLOG+1][MAXN][2];
vector<vector<int>> adj;
int n, m;
pair<int,int> pai(pair<int,int> u) {
  int e = 0;
  if (u.second == 1 and (int)adj[u.first].size() > 1) { // já veio de grande
    e = 1;
  }
  int v = adj[u.first][e];
  bool is_v_biggest = false;
  if (adj[v][0] == u.first) is_v_biggest = true;
  return {v, is_v_biggest};
};
pair<int,int> move(pair<int,int> v, int step) {
  for (int b=MAXLOG; b>=0; b--) {
    if ((1 << b) > step) continue;
    step -= (1 << b);
    v = f[b][v.first][v.second];
  }
  return v;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
  n = N; m = M;
  adj = vector<vector<int>>(n);
  for (int e=0; e<m; e++) {
    int u = R[e][0], v = R[e][1];
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (int i=0; i<n; i++) {
    for (int state=0; state<=1; state++) {
      f[0][i][state] = pai({i, state});
    }
  }
  for (int b=1; b<=MAXLOG; b++) {
    for (int i=0; i<n; i++) {
      for (int state=0; state<=1; state++) {
        pair<int,int> mid = f[b-1][i][state];
        f[b][i][state] = f[b-1][mid.first][mid.second];
      }
    }
  }
  for(int g=0; g<Q; g++) {
    int ans = 0;
    for (int i=0; i<n; i++) {
      pair<int,int> dest = move({i, 0}, G[g]);
      if (dest.first == P) {
        ans++;
      }
    }
    answer(ans);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1216 KB Output is correct
3 Correct 1 ms 1220 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 2 ms 1372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1216 KB Output is correct
3 Correct 1 ms 1220 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 2 ms 1372 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 11 ms 13088 KB Output is correct
12 Correct 29 ms 22108 KB Output is correct
13 Correct 37 ms 48120 KB Output is correct
14 Correct 68 ms 76424 KB Output is correct
15 Correct 70 ms 77392 KB Output is correct
16 Correct 55 ms 52928 KB Output is correct
17 Correct 47 ms 45244 KB Output is correct
18 Correct 25 ms 21852 KB Output is correct
19 Correct 68 ms 76368 KB Output is correct
20 Correct 70 ms 77396 KB Output is correct
21 Correct 55 ms 53072 KB Output is correct
22 Correct 50 ms 45148 KB Output is correct
23 Correct 84 ms 84560 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1216 KB Output is correct
3 Correct 1 ms 1220 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 2 ms 1372 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 11 ms 13088 KB Output is correct
12 Correct 29 ms 22108 KB Output is correct
13 Correct 37 ms 48120 KB Output is correct
14 Correct 68 ms 76424 KB Output is correct
15 Correct 70 ms 77392 KB Output is correct
16 Correct 55 ms 52928 KB Output is correct
17 Correct 47 ms 45244 KB Output is correct
18 Correct 25 ms 21852 KB Output is correct
19 Correct 68 ms 76368 KB Output is correct
20 Correct 70 ms 77396 KB Output is correct
21 Correct 55 ms 53072 KB Output is correct
22 Correct 50 ms 45148 KB Output is correct
23 Correct 84 ms 84560 KB Output is correct
24 Correct 5 ms 856 KB Output is correct
25 Correct 2173 ms 13148 KB Output is correct
26 Correct 4586 ms 22120 KB Output is correct
27 Correct 4632 ms 48304 KB Output is correct
28 Execution timed out 5033 ms 76504 KB Time limit exceeded
29 Halted 0 ms 0 KB -