Submission #1008814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008814		gustavo_d	Tropical Garden (IOI11_garden)	C++17	100 / 100	3673 ms	36680 KiB

garden

// 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;
      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]) {
    for (int i=0; i<2*n; i++) {
      if (i & 1) continue;
      if (cycle_idx[i] != cycle_idx[dest]) continue;
      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;
      }
    }
  } else {
    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();

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

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31