Submission #1153575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153575		hiderr	열대 식물원 (Tropical Garden) (IOI11_garden)	C++20	0 / 100	0 ms	576 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pb push_back

using ll = long long;
int n, m, p, q;

vector<vector<pair<int, int>>> min_edge;
vector<vector<pair<int, int>>> graph;
vector<vector<int>> edges;
vector<int> act;

vector<int> D, C;

int get_dest(pair<int, int> edge) {
  return edges[edge.first][edge.second];
}

pair<int, int> get_next(pair<int, int> edge) {
  int v = get_dest(edge);
  if(edge.first != min_edge[v][0].first) {
    return min_edge[v][0];
  }
  else {
    return min_edge[v][1];
  }
}

int get_id(pair<int, int> edge) {
  return edge.first + (m * edge.second);
}

constexpr int UNVISITED = (-1);
constexpr int UNREACHABLE = (1e9);
int timer = 0;

void dfs_cyc(pair<int, int> edge) {
  int id = get_id(edge);
  act[id] = ++timer;
  auto nxt = get_next(edge);
  int nxt_id = get_id(nxt);
  if(act[nxt_id]) {
    C[id] = C[nxt_id] = (act[id] - act[nxt_id]) + 1;
  }
  else {
    if(C[nxt_id] == UNVISITED) {
      dfs_cyc(nxt);
    }
  }
  C[id] = C[nxt_id];
  act[id] = 0;
}

void dfs(pair<int, int> edge) {
  int v = get_dest(edge);
  int id = get_id(edge);
  D[id] = UNREACHABLE;
  if(v == p) {
    D[id] = 1;
    return;
  }
  auto nxt = get_next(edge);
  int new_id = get_id(nxt);
  if(D[new_id] == UNVISITED) {
    dfs(nxt);
  }
  if(D[new_id] == UNREACHABLE) {
    D[id] = UNREACHABLE;
  }
  else {
    D[id] = D[new_id] + 1;
  }
}

void count_routes(int N, int M, int P, int _edges[][2], int Q, int _G[]) {

  n = N, m = M, p = P, q = Q;

  edges.resize(m, vector<int>(2));
  
  loop(i, 0, m-1) {
    loop(j, 0, 1) {
      edges[i][j] = _edges[i][j];
    }
  }

  graph.resize(n);

  loop(i, 0, m-1) {
    int a = edges[i][0];
    int b = edges[i][1];
    graph[a].pb({ i, 1 });
    graph[b].pb({ i, 0 });
  }

  min_edge.resize(n, vector<pair<int, int>>(2, { 1e9, (-1) }));
  D.resize(2 * m, UNVISITED);
  C.resize(2 * m, UNVISITED);
  act.resize(2 * m, 0);

  loop(i, 0, n-1) {
    for(pair<int, int> state : graph[i]) {
      if(state < min_edge[i][0]) {
        min_edge[i][1] = min_edge[i][0];
        min_edge[i][0] = state;
      }
      else if(state < min_edge[i][1]) {
        min_edge[i][1] = state;
      }
    }
    if(sz(graph[i]) == 1) {
      min_edge[i][1] = min_edge[i][0];
    }
  }

  loop(i, 0, n-1) {
    dfs_cyc(min_edge[i][0]);
  }

  loop(i, 0, n-1) {
    auto e = min_edge[i][0];
    if(D[get_id(e)] == UNVISITED) {
      dfs(e);
    }
  }

  // loop(i, 0, n-1) {
  //   int id = get_id(min_edge[i][0]);
  //   // cout << "dist_from_p[" << i << "] = " << D[id]  << ", " << "cycle_len[" << i << "] = " << C[id]  << '\n';
  // }

  loop(qi, 0, q-1) {
    int k = _G[qi];
    if(k == 0) {
      answer(1);
      continue;
    }
    int res = 0;
    loop(i, 0, n-1) {
      int id = get_id(min_edge[i][0]);
      int d = D[id];
      int c = C[id];
      if(k % c == d % c) {
        ++res;
      }
    }
    answer(res);
  }

}

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