Submission #1153652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153652		hiderr	Tropical Garden (IOI11_garden)	C++20	100 / 100	4827 ms	49756 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> D1, D2, L, 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 = (-2e9);
constexpr int UNREACHABLE = (2e9);
int timer = 0;

int sgn(int val) {
  if(val < 0) return (-1);
  if(val == 0) return 0;
  return 1;
}

int lo =  1e9;

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;
    lo = act[nxt_id];
  }
  else {
    if(C[nxt_id] == UNVISITED) {
      dfs_cyc(nxt);
    }
  }
  if(act[id] >= lo) {
    L[id] = 1;
  }
  if(lo == act[id]) {
    lo = 1e9;
  }
  C[id] = C[nxt_id];
  act[id] = 0;
}

void dfs1(pair<int, int> edge) {
  int v = get_dest(edge);
  int id = get_id(edge);
  D1[id] = UNREACHABLE;
  if(v == p && edge.first == min_edge[v][0].first) {
    if(L[id] || L[get_id(get_next(edge))]) {
      D1[id] = 1;
    }
    else {
      D1[id] = (-1);
    }
    return;
  }
  auto nxt = get_next(edge);
  int new_id = get_id(nxt);
  if(D1[new_id] == UNVISITED) {
    dfs1(nxt);
  }
  if(D1[new_id] == UNREACHABLE) {
    D1[id] = UNREACHABLE;
  }
  else {
    D1[id] = D1[new_id] + sgn(D1[new_id]);
  }
}

void dfs2(pair<int, int> edge) {
  int v = get_dest(edge);
  int id = get_id(edge);
  D2[id] = UNREACHABLE;
  if(v == p && edge.first != min_edge[v][0].first) {
    if(L[id] || L[get_id(get_next(edge))]) {
      D2[id] = 1;
    }
    else {
      D2[id] = (-1);
    }
    return;
  }
  auto nxt = get_next(edge);
  int new_id = get_id(nxt);
  if(D2[new_id] == UNVISITED) {
    dfs2(nxt);
  }
  if(D2[new_id] == UNREACHABLE) {
    D2[id] = UNREACHABLE;
  }
  else {
    D2[id] = D2[new_id] + sgn(D2[new_id]);
  }
}

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) }));
  D1.resize(2 * m, UNVISITED);
  D2.resize(2 * m, UNVISITED);
  C.resize(2 * m, UNVISITED);
  act.resize(2 * m, 0);
  L.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(D1[get_id(e)] == UNVISITED) {
      dfs1(e);
    }
    if(D2[get_id(e)] == UNVISITED) {
      dfs2(e);
    }
    assert(D2[get_id(e)] != UNVISITED);
  }

  loop(i, 0, n-1) {
    int id = get_id(min_edge[i][0]);
    cerr << "D1[" << i << "] = " << D1[id]  << ", " << "D2[" << i << "] = " << D2[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]);
      bool cool = false;
      {
        int d = D1[id];
        if(d != UNREACHABLE) {
          int c = C[id];
          if(d > 0) {
            if(k % c == d % c && d <= k) {
              cool = true;
              ++res;
            }
          }
          else {
            if(k == -d) {
              cool = true;
              ++res;
            }
          }
        }
      }
      if(!cool) {
        int d = D2[id];
        if(d != UNREACHABLE) {
          int c = C[id];
          if(d > 0) {
            if(k % c == d % c && d <= k) {
              ++res;
            }
          }
          else {
            if(k == -d) {
              ++res;
            }
          }
        }
      }
    }
    answer(res);
  }

}

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