Submission #1113104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113104		ortsac	Tropical Garden (IOI11_garden)	C++17	100 / 100	114 ms	73764 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second

struct Edge {
  int idx, to;

  Edge(int a = 0, int b = 0) : idx(a), to(b) {}

  bool operator < (const Edge& a) const {
    return (idx < a.idx);
  }
};

const int MAXN = 3e5 + 10;
const int INF = 0x3f3f3f3f;
const int MAXLOG = 30;
int n, m, p;

vector<Edge> adj1[MAXN];
pii nxt[MAXN][2];
pii binl[30][MAXN][2];
int mi[MAXN];
vector<pii> adj[MAXN][2];
int dist[2][MAXN][2];
int vis[MAXN][2];
// first is tam, second is if its included
pii pV[2];
int qtd[MAXN];
int qtdM[MAXN];

void init(int q) {
  memset(vis, 0, sizeof vis);
  pii curr = {p, q};
  while (vis[curr.fr][curr.se] != 2) {
    vis[curr.fr][curr.se]++;
    curr = nxt[curr.fr][curr.se];
  }
  if (vis[p][q] == 2) {
    pV[q].se = 1;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) if (vis[i][j]) pV[q].fr++;
  }
}


void count_routes(int32_t N, int32_t M, int32_t P, int32_t R[][2], int32_t Q, int32_t G[])
{
  n = N;
  m = M;
  p = P;
  for (int i = 0; i < n; i++) {
    mi[i] = INF;
    dist[0][i][0] = dist[0][i][1] = INF;
    dist[1][i][0] = dist[1][i][1] = INF;
  }
  for (int i = 0; i < m; i++) {
    int a = R[i][0], b = R[i][1];
    adj1[a].push_back(Edge(i, b));
    adj1[b].push_back(Edge(i, a));
    mi[a] = min(mi[a], i);
    mi[b] = min(mi[b], i);
  }
  for (int i = 0; i < n; i++) {
    sort(adj1[i].begin(), adj1[i].end());
  }
  for (int i = 0; i < n; i++) {
    // faz o do 0
    bool f = 0;
    if (mi[adj1[i][0].to] == adj1[i][0].idx) f = 1;
    nxt[i][0] = make_pair(adj1[i][0].to, f);
    // faz o do 1
    if (((int) adj1[i].size()) == 1) {
      nxt[i][1] = nxt[i][0];
    } else {
      f = 0;
      if (mi[adj1[i][1].to] == adj1[i][1].idx) f = 1;
      nxt[i][1] = make_pair(adj1[i][1].to, f);
    }
  }
  // fazer nova adj
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      pii a = nxt[i][j];
      adj[a.fr][a.se].push_back({i, j});
    }
  }
  // calcular a distância de todo mundo até o p
  for (int b = 0; b < 2; b++) {
    dist[b][p][b] = 0;
    queue<pii> q;
    q.push({p, b});
    while (!q.empty()) {
      auto u = q.front();
      q.pop();
      for (auto v : adj[u.fr][u.se]) {
        if (dist[b][v.fr][v.se] != INF) continue;
        dist[b][v.fr][v.se] = (dist[b][u.fr][u.se] + 1);
        q.push(v);
      }
    }
  }
  // tá legal, agora sei a distância de todo mundo
  init(0);
  init(1);
  vector<int> ans(Q);
  vector<pii> queries;
  for (int i = 0; i < Q; i++) {
    queries.push_back({G[i], i});
  }
  sort(queries.begin(), queries.end());
  // calcular resposta pro p[0]
  for (int b = 0; b < 2; b++) {
    memset(qtd, 0, sizeof qtd);
    memset(qtdM, 0, sizeof qtdM);
    vector<int> c;
    for (int i = 0; i < n; i++) {
      c.push_back(dist[b][i][0]);
    }
    sort(c.begin(), c.end());
    int curr = 0;
    for (int i = 0; i < Q; i++) {
      while ((curr < ((int)c.size())) && (c[curr] <= queries[i].fr)) {
        if (c[curr] < MAXN) qtd[c[curr]]++;
        qtdM[c[curr] % pV[b].fr]++;
        curr++;
      }
      if (pV[b].se) {
        // tá no ciclo
        ans[queries[i].se] += qtdM[queries[i].fr % pV[b].fr];
      } else {
        if (queries[i].fr < MAXN) ans[queries[i].se] += qtd[queries[i].fr];
      }
    }
  }
  for (auto u : ans) answer(u);
}

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