제출 #1206762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206762		shrey2091	Tropical Garden (IOI11_garden)	C++20	100 / 100	67 ms	47684 KiB

garden

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

const int MXN = 3e5+5;

int n, f[MXN];
vector<int> g[MXN], gg[MXN];

bool vis[MXN];
int cyc;

void dfs(int r, int v, int d = 0) {
  vis[v] = 1;
  if(!vis[f[v]]) dfs(r, f[v], d+1);
  else if(f[v]==r) cyc = d+1;
}

struct solver {
  int cc;
  vector<vector<int>> vec;
  int cnt[MXN];
  int dis[MXN];

  solver(int v) {
    fill(vis, vis + n + n, 0);
    cyc = 0;
    dfs(v, v);
    vec.resize(cc = cyc);

    fill(dis, dis+n+n, -1);
    memset(cnt, 0, sizeof(cnt));
    dis[v] = 0;
    if(v<n) cnt[0]++;
    queue<int> q;
    q.push(v);
    if(v<n && cc) vec[0].push_back(0);
    while(!q.empty()) {
      v = q.front();
      q.pop();
      for(int u : gg[v]) {
        if(dis[u]==-1) {
          dis[u] = dis[v]+1;
          if(u<n) cnt[dis[u]]++;
          q.push(u);
          if(u<n && cc) vec[dis[u]%cc].push_back(dis[u]);
        }
      }
    }
  }
  int get(int k) {
    if(!cc) return k>=MXN ? 0 : cnt[k];
    return upper_bound(vec[k%cc].begin(), vec[k%cc].end(), k)-vec[k%cc].begin();
  }
};

void count_routes(int n, int m, int P, int R[][2], int Q, int G[]) {
  ::n = n;
  for(int i = 0; i < m; i++) {
    g[R[i][0]].push_back(R[i][1]);
    g[R[i][1]].push_back(R[i][0]);
  }
  for(int i = 0; i < n; i++) {
    f[i] = g[i][0] + (g[g[i][0]][0] == i ? n : 0);
    if(g[i].size() == 1) f[i + n] = f[i];
    else f[i + n] = g[i][1] + (g[g[i][1]][0] == i ? n : 0);
  }
  for(int i = 0; i < n + n; i++) gg[f[i]].push_back(i);
  solver A(P), B(P + n);
  for(int i = 0; i < Q; i++) answer(A.get(G[i]) + B.get(G[i]));
}

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