oj.uz

Submission #1008812

# Submission time Handle Problem Language Result Execution time Memory
1008812 2024-06-26T20:03:29 Z gustavo_d Tropical Garden (IOI11_garden) C++17
100 / 100
 3497 ms 37968 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;

vector<vector<int>> adj;
int pai[2*MAXN];
vector<int> pai_inv[2*MAXN];
bool in_cycle[2*MAXN];
int cycle_pai[2*MAXN];
int nivel[2*MAXN];
int cycle_sz[2*MAXN];
int in_grau[2*MAXN];
int state[2*MAXN];
int cycle_idx[2*MAXN];
int idx_in_cycle[2*MAXN];
bool mark[2*MAXN];
int qty_cycles = 0;

int n, m;

void map_cycle(int src) {
  int cycle_id = qty_cycles++;
  int v = src;
  int v_idx_in_cycle = 0;
  while (state[v] == 0) {
    state[v] = 2;
    in_cycle[v] = true;
    cycle_pai[v] = v;
    nivel[v] = 0;
    cycle_idx[v] = cycle_id;
    idx_in_cycle[v] = v_idx_in_cycle;
    cycle_sz[cycle_id]++;

    v = pai[v];
    v_idx_in_cycle++;
  }
}

void top_sort() {
  queue<int> rm; vector<int> top_order;
  for (int i=0; i<2*n; i++) {
    if (in_grau[i] == 0) rm.push(i);
  }

  while (!rm.empty()) {
    int v = rm.front(); rm.pop();
    top_order.push_back(v);
    in_grau[pai[v]]--;
    if (in_grau[pai[v]] == 0) rm.push(pai[v]);

    state[v] = 3; in_cycle[v] = false;
  }

  for (int i=0; i<2*n; i++) {
    if (state[i] == 0) {
      map_cycle(i);
    }
  }

  for (int i=(int)top_order.size()-1; i>=0; i--) {
    int v = top_order[i];
    cycle_pai[v] = cycle_pai[pai[v]];
    nivel[v] = nivel[pai[v]]+1;
    cycle_idx[v] = cycle_idx[pai[v]];
    idx_in_cycle[v] = -1;
  }
}

pair<int,int> calc_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};
};

int cycle_dist(int u, int v) { // u até v
  int sz = cycle_sz[cycle_idx[u]];
  int idx_u = idx_in_cycle[u];
  int idx_v = idx_in_cycle[v];
  if (idx_u <= idx_v) return idx_v - idx_u;
  else return (sz - idx_u + idx_v);
}

void BFS(int src, int nivel_target) {
  bool vis[2*n];
  for (int i=0; i<2*n; i++) vis[i] = false;
  queue<int> visit;
  vis[src] = true;
  visit.push(src);
  while (!visit.empty()) {
    int v = visit.front(); visit.pop();
    if (nivel[v] == nivel_target and (v&1)==0) {
      mark[v] = true;
      // cout << "got " << v << endl;
      continue;
    }
    for (int viz : pai_inv[v]) {
      if (vis[viz]) continue;
      vis[viz] = true;
      visit.push(viz);
    }
  }
}

void mark_ans(int dest, int steps) {
  if (in_cycle[dest]) {
    // cout << dest << " c" << endl;
    for (int i=0; i<2*n; i++) {
      if (i & 1) continue;
      if (cycle_idx[i] != cycle_idx[dest]) continue;
      // // cout << "dist" << endl;
      int first = nivel[i] + cycle_dist(cycle_pai[i], dest);
      if (steps < first) continue;
      if (((steps - first) % cycle_sz[cycle_idx[dest]]) == 0) {
        mark[i] = true;
        // cout << "got " << i << ' ' << steps << ' ' <<  first << ' ' << cycle_sz[cycle_idx[dest]] << endl;
      }// } else cout << "not got " << i << ' ' << steps << ' ' << first << ' ' << cycle_sz[cycle_idx[dest]] << endl;
    }
    // // cout << "end" << endl;
  } else {
    // cout << dest << " nc" << endl;
    BFS(dest, steps+nivel[dest]);
  }
}

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;
  for (int i=0; i<2*n; i++) {
    pai_inv[i].clear();
    in_grau[i] = 0;
    state[i] = 0;
    cycle_sz[i] = 0;
  }
  adj = vector<vector<int>>(n);
  qty_cycles = 0;
  
  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 stat=0; stat<=1; stat++) {
      int idx = 2*i + stat;
      pair<int,int> pai_aux = calc_pai({i, stat});
      pai[idx] = 2*pai_aux.first + pai_aux.second;
      in_grau[pai[idx]]++;
      pai_inv[pai[idx]].push_back(idx);
    }
  }

  top_sort();

  // // cout << "ok" << endl;

  for(int g=0; g<Q; g++) {
    // quantos lugares saem e chegam em P
    // cout << "debugging " << g << " ans" << endl;
    int ans = 0;
    mark_ans(2*P, G[g]);
    // // cout << 1 << endl;
    mark_ans(2*P+1, G[g]);
    // // cout << 2 << endl;
    for (int i=0; i<2*n; i++) {
      ans += mark[i];
      // if (mark[i]) cout << i << "foi" << endl;
      mark[i] = false;
    }
    // // cout << 3 << endl;
    answer(ans);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 4 ms 7772 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7512 KB Output is correct
6 Correct 4 ms 7772 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 4 ms 7768 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 4 ms 7772 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7512 KB Output is correct
6 Correct 4 ms 7772 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 4 ms 7768 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 11 ms 11888 KB Output is correct
12 Correct 22 ms 14808 KB Output is correct
13 Correct 27 ms 24668 KB Output is correct
14 Correct 76 ms 32712 KB Output is correct
15 Correct 79 ms 33220 KB Output is correct
16 Correct 65 ms 25804 KB Output is correct
17 Correct 54 ms 23444 KB Output is correct
18 Correct 22 ms 14792 KB Output is correct
19 Correct 86 ms 32708 KB Output is correct
20 Correct 75 ms 33216 KB Output is correct
21 Correct 57 ms 25800 KB Output is correct
22 Correct 55 ms 23496 KB Output is correct
23 Correct 77 ms 35064 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 4 ms 7772 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7512 KB Output is correct
6 Correct 4 ms 7772 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 4 ms 7768 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 11 ms 11888 KB Output is correct
12 Correct 22 ms 14808 KB Output is correct
13 Correct 27 ms 24668 KB Output is correct
14 Correct 76 ms 32712 KB Output is correct
15 Correct 79 ms 33220 KB Output is correct
16 Correct 65 ms 25804 KB Output is correct
17 Correct 54 ms 23444 KB Output is correct
18 Correct 22 ms 14792 KB Output is correct
19 Correct 86 ms 32708 KB Output is correct
20 Correct 75 ms 33216 KB Output is correct
21 Correct 57 ms 25800 KB Output is correct
22 Correct 55 ms 23496 KB Output is correct
23 Correct 77 ms 35064 KB Output is correct
24 Correct 4 ms 7516 KB Output is correct
25 Correct 198 ms 11864 KB Output is correct
26 Correct 307 ms 14808 KB Output is correct
27 Correct 1081 ms 25124 KB Output is correct
28 Correct 1378 ms 32712 KB Output is correct
29 Correct 1706 ms 33472 KB Output is correct
30 Correct 947 ms 25804 KB Output is correct
31 Correct 1002 ms 23496 KB Output is correct
32 Correct 190 ms 15060 KB Output is correct
33 Correct 1380 ms 32712 KB Output is correct
34 Correct 1654 ms 33188 KB Output is correct
35 Correct 707 ms 25804 KB Output is correct
36 Correct 3497 ms 23500 KB Output is correct
37 Correct 1285 ms 35276 KB Output is correct
38 Correct 2826 ms 37968 KB Output is correct