Submission #1261775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261775		goulthen	Tropical Garden (IOI11_garden)	C++20	100 / 100	1326 ms	33364 KiB

garden

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

#define rep(i,a,b) for (int i = a; i <= b; i++)
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second

const int MAXN = 2e5+10;
const int INF = 1e9 + 5;
vector<pii> g[MAXN];
vector<int> g2[2*MAXN];
int p[2*MAXN], dist[2*MAXN][2];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  rep(i,0,M-1) {
    g[R[i][0]].pb({R[i][1],i});
    g[R[i][1]].pb({R[i][0],i});
  }

  rep(i,0,N-1) {
    pii b = g[i][0], b2 = {-1,-1};
    if (g[i].size()>1) b2 = g[i][1];
    if (b.se != g[b.fi][0].se) {
      p[i] = b.fi;
      if (b2.fi==-1) p[i+N] = b.fi;
    }
    else {
      p[i] = b.fi + N;
      if (b2.fi==-1) p[i+N] = b.fi + N;
    }
    if (b2.se==-1) continue;

    if (b2.se != g[b2.fi][0].se) p[i+N] = b2.fi;
    else p[i+N] = b2.fi + N;
  }

  rep(i,0,2*N-1) g2[p[i]].pb(i);
  rep(i,0,2*N-1) rep(j,0,1) dist[i][j] = INF;

  int cc = P;
  rep(t,0,1) {
    queue<pii> bfs;
    bfs.push({0,cc});
    while (!bfs.empty()) {
      auto [d, u] = bfs.front();
      bfs.pop();
      if (dist[u][t]!=INF) continue;
      dist[u][t] = d;

      for (int &v : g2[u]) {
        bfs.push({d+1,v});
      }
    }
    cc+=N;
  }

  const auto gc = [&](int u) -> int {
    int len = 0;
    vector<bool> vis(2*N, 0);

    int cur = u;
    while (!vis[cur]) {
      vis[cur] = 1;
      len++;
      cur = p[cur];
    }

    if (cur != u) return INF;
    return len;
  };

  int s1 = gc(P), s2 = gc(P+N);

  rep(i,0,Q-1) {
    int k = G[i], ans = 0;
    rep(i,0,N-1) {
      //cout << i << ' ' << dist[i][0] << ' ' << s1 << '\n';
      if (dist[i][0] <= k && (k-dist[i][0])%s1 == 0) ans++;
      else if (dist[i][1] <= k && (k-dist[i][1])%s2 == 0) ans++;
    }

    answer(ans);
  }
}

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