Submission #1312756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312756		tsetsenbileg	Tropical Garden (IOI11_garden)	C++20	100 / 100	932 ms	46384 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
#define pr pair<int, int>
#define pb push_back
using namespace std;
const ll INF = 1e18+1, MOD = 1e9+7;
vector<vector<int>> edge;
vector<vector<pr>> dist; // dist from the node to the p, first path used or not (1 for used, 0 for not)
vector<vector<bool>> vis, badvis;
int p;

pr find(int node, int prev) {
  if (node == p) {
    if (edge[node][0] == prev) return {0, 1}; // went to the p using the beautiful path
    else return {0, 0}; // went to the p without using the first path, thus 
  }
  pr res;
  int used = (edge[node][0] == prev);
  if (vis[node][used] || badvis[node][used]) {
    badvis[node][used] = 1;
    return {-1, -1}; // useless loop
  }
  vis[node][used] = 1;
  if (dist[node][used].first != -1) {
    vis[node][used] = 0;
    return dist[node][used];
  }
  else {
    if (used && edge[node].size() > 1) {
      res = find(edge[node][1], node);
    }
    else {
      res = find(edge[node][0], node);
    }
  }
  if (res == make_pair(-1, -1)) {
    vis[node][used] = 0;
    badvis[node][used] = 1;
    return dist[node][used] = {-1, -1};
  }
  vis[node][used] = 0;
  return dist[node][used] = {res.first+1, res.second};
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  p = P;
  vector<int> ans(Q, 0);
  edge.assign(N, vector<int>());
  dist.assign(N, vector<pr>(2, {-1, -1}));
  vis.assign(N, vector<bool>(2, 0));
  badvis.assign(N, vector<bool>(2, 0));
  for (int i = 0; i < M; i++) {
    edge[R[i][0]].pb(R[i][1]);
    edge[R[i][1]].pb(R[i][0]);
  }
  for (int i = 0; i < N; i++) {
    // vis.assign(N, vector<bool>(2, 0));
    if (dist[i][0].first == -1) {
      find(i, -1);
    }
    // vis.assign(N, vector<bool>(2, 0));
    if (dist[i][1].first == -1) {
      find(i, edge[i][0]);
    } 
  }
  pr temp1 = find(edge[p][0], p);
  pr temp2 = find(((edge[p].size() > 1) ? edge[p][1] : edge[p][0]), p);
  dist[p][0] = {temp1.first + 1, temp1.second};  // from state 0, go to edge[p][1]
  dist[p][1] = {temp2.first + 1, temp2.second};  // from state 1, go to edge[p][0]
  int cycle[2];
  cycle[0] = dist[p][0].first;
  cycle[1] = dist[p][1].first;
  if (cycle[0] == 0) cycle[0] = -1;
  if (cycle[1] == 0) cycle[1] = -1;
  int next[2];
  next[0] = dist[p][0].second;
  next[1] = dist[p][1].second;
  for (int i = 0; i < Q; i++) {
    int res = 0;
    for (int j = 0; j < N; j++) {
      int k = G[i];
      if (dist[j][0].first == -1) continue;
      k -= dist[j][0].first;
      if (k < 0) continue;
      if (k == 0) {res++; continue;}
      int used = dist[j][0].second;
      if (cycle[used] == -1) continue;
      k -= cycle[used];
      used = next[used];
      if (k == 0) {res++; continue;}
      if (k < 0) continue;
      if (next[used] == used && cycle[used] > 0) {
        if (next[used] == -1) continue;
        k %= cycle[used];
      }
      else {
        if (cycle[0] == -1 || cycle[1] == -1) continue;
        k %= (cycle[0] + cycle[1]);
        if (k > 0) k -= cycle[used];
      }
      if (k == 0) res++;
    }
    ans[i] = res;
  }
  for(int i=0; i<Q; i++)
    answer(ans[i]);
}

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