oj.uz

Submission #1113104

# Submission time Handle Problem Language Result Execution time Memory
1113104 2024-11-15T18:27:15 Z ortsac Tropical Garden (IOI11_garden) C++17
100 / 100
 114 ms 73764 KB 
#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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 39504 KB Output is correct
2 Correct 6 ms 39504 KB Output is correct
3 Correct 7 ms 39740 KB Output is correct
4 Correct 6 ms 39432 KB Output is correct
5 Correct 6 ms 39504 KB Output is correct
6 Correct 7 ms 39760 KB Output is correct
7 Correct 8 ms 39376 KB Output is correct
8 Correct 7 ms 39504 KB Output is correct
9 Correct 7 ms 39920 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 39504 KB Output is correct
2 Correct 6 ms 39504 KB Output is correct
3 Correct 7 ms 39740 KB Output is correct
4 Correct 6 ms 39432 KB Output is correct
5 Correct 6 ms 39504 KB Output is correct
6 Correct 7 ms 39760 KB Output is correct
7 Correct 8 ms 39376 KB Output is correct
8 Correct 7 ms 39504 KB Output is correct
9 Correct 7 ms 39920 KB Output is correct
10 Correct 7 ms 39504 KB Output is correct
11 Correct 18 ms 44560 KB Output is correct
12 Correct 32 ms 49060 KB Output is correct
13 Correct 53 ms 58800 KB Output is correct
14 Correct 96 ms 66132 KB Output is correct
15 Correct 107 ms 69468 KB Output is correct
16 Correct 83 ms 60988 KB Output is correct
17 Correct 78 ms 60012 KB Output is correct
18 Correct 30 ms 48948 KB Output is correct
19 Correct 86 ms 67164 KB Output is correct
20 Correct 114 ms 69540 KB Output is correct
21 Correct 78 ms 60912 KB Output is correct
22 Correct 83 ms 59304 KB Output is correct
23 Correct 107 ms 69836 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 39504 KB Output is correct
2 Correct 6 ms 39504 KB Output is correct
3 Correct 7 ms 39740 KB Output is correct
4 Correct 6 ms 39432 KB Output is correct
5 Correct 6 ms 39504 KB Output is correct
6 Correct 7 ms 39760 KB Output is correct
7 Correct 8 ms 39376 KB Output is correct
8 Correct 7 ms 39504 KB Output is correct
9 Correct 7 ms 39920 KB Output is correct
10 Correct 7 ms 39504 KB Output is correct
11 Correct 18 ms 44560 KB Output is correct
12 Correct 32 ms 49060 KB Output is correct
13 Correct 53 ms 58800 KB Output is correct
14 Correct 96 ms 66132 KB Output is correct
15 Correct 107 ms 69468 KB Output is correct
16 Correct 83 ms 60988 KB Output is correct
17 Correct 78 ms 60012 KB Output is correct
18 Correct 30 ms 48948 KB Output is correct
19 Correct 86 ms 67164 KB Output is correct
20 Correct 114 ms 69540 KB Output is correct
21 Correct 78 ms 60912 KB Output is correct
22 Correct 83 ms 59304 KB Output is correct
23 Correct 107 ms 69836 KB Output is correct
24 Correct 8 ms 39504 KB Output is correct
25 Correct 17 ms 44528 KB Output is correct
26 Correct 32 ms 49056 KB Output is correct
27 Correct 50 ms 58656 KB Output is correct
28 Correct 86 ms 62872 KB Output is correct
29 Correct 106 ms 71348 KB Output is correct
30 Correct 84 ms 62448 KB Output is correct
31 Correct 74 ms 60772 KB Output is correct
32 Correct 28 ms 49604 KB Output is correct
33 Correct 86 ms 68892 KB Output is correct
34 Correct 92 ms 71580 KB Output is correct
35 Correct 71 ms 62456 KB Output is correct
36 Correct 73 ms 61540 KB Output is correct
37 Correct 89 ms 70704 KB Output is correct
38 Correct 94 ms 73764 KB Output is correct