oj.uz

Submission #1002792

# Submission time Handle Problem Language Result Execution time Memory
1002792 2024-06-19T19:44:32 Z gustavo_d Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 84308 KB 
// https://oj.uz/problem/view/IOI11_garden > p326
#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[])
{
  /*
  • P – destino que conta se chegar
  • R[M][2] – arestas ordenadas de forma decrescente pela beleza (são distintas)
  • G[Q] qnts arestas cada grupo passará.
  */
  n = N; m = M;
  adj = vector<vector<int>>(n);
  for (int e=0; e<m; e++) {
    // já ficam ordenadas
    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++) {
    // quantos lugares saem e chegam em P
    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 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 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 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 13 ms 13148 KB Output is correct
12 Correct 30 ms 21900 KB Output is correct
13 Correct 39 ms 48088 KB Output is correct
14 Correct 79 ms 76372 KB Output is correct
15 Correct 83 ms 77396 KB Output is correct
16 Correct 66 ms 53100 KB Output is correct
17 Correct 50 ms 45060 KB Output is correct
18 Correct 32 ms 21844 KB Output is correct
19 Correct 77 ms 76372 KB Output is correct
20 Correct 89 ms 77256 KB Output is correct
21 Correct 64 ms 53112 KB Output is correct
22 Correct 49 ms 45140 KB Output is correct
23 Correct 85 ms 84308 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 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 13 ms 13148 KB Output is correct
12 Correct 30 ms 21900 KB Output is correct
13 Correct 39 ms 48088 KB Output is correct
14 Correct 79 ms 76372 KB Output is correct
15 Correct 83 ms 77396 KB Output is correct
16 Correct 66 ms 53100 KB Output is correct
17 Correct 50 ms 45060 KB Output is correct
18 Correct 32 ms 21844 KB Output is correct
19 Correct 77 ms 76372 KB Output is correct
20 Correct 89 ms 77256 KB Output is correct
21 Correct 64 ms 53112 KB Output is correct
22 Correct 49 ms 45140 KB Output is correct
23 Correct 85 ms 84308 KB Output is correct
24 Correct 5 ms 604 KB Output is correct
25 Correct 2260 ms 13288 KB Output is correct
26 Correct 4675 ms 22120 KB Output is correct
27 Correct 4881 ms 48312 KB Output is correct
28 Execution timed out 5047 ms 76256 KB Time limit exceeded
29 Halted 0 ms 0 KB -