oj.uz

Submission #1113103

# Submission time Handle Problem Language Result Execution time Memory
1113103 2024-11-15T18:23:28 Z ortsac Tropical Garden (IOI11_garden) C++17
69 / 100
 88 ms 47208 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 = 150010;
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 4 ms 25168 KB Output is correct
2 Correct 4 ms 25168 KB Output is correct
3 Correct 4 ms 25168 KB Output is correct
4 Correct 4 ms 25340 KB Output is correct
5 Correct 5 ms 25236 KB Output is correct
6 Correct 5 ms 25424 KB Output is correct
7 Correct 4 ms 25168 KB Output is correct
8 Correct 5 ms 25168 KB Output is correct
9 Correct 6 ms 25680 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25168 KB Output is correct
2 Correct 4 ms 25168 KB Output is correct
3 Correct 4 ms 25168 KB Output is correct
4 Correct 4 ms 25340 KB Output is correct
5 Correct 5 ms 25236 KB Output is correct
6 Correct 5 ms 25424 KB Output is correct
7 Correct 4 ms 25168 KB Output is correct
8 Correct 5 ms 25168 KB Output is correct
9 Correct 6 ms 25680 KB Output is correct
10 Correct 5 ms 25168 KB Output is correct
11 Correct 13 ms 30236 KB Output is correct
12 Correct 25 ms 32676 KB Output is correct
13 Correct 46 ms 40344 KB Output is correct
14 Correct 73 ms 46816 KB Output is correct
15 Correct 88 ms 47208 KB Output is correct
16 Correct 72 ms 42392 KB Output is correct
17 Correct 68 ms 41708 KB Output is correct
18 Correct 22 ms 32468 KB Output is correct
19 Correct 72 ms 46668 KB Output is correct
20 Correct 87 ms 47200 KB Output is correct
21 Correct 65 ms 42480 KB Output is correct
22 Correct 67 ms 37112 KB Output is correct
23 Correct 85 ms 46648 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 25168 KB Output is correct
2 Correct 4 ms 25168 KB Output is correct
3 Correct 4 ms 25168 KB Output is correct
4 Correct 4 ms 25340 KB Output is correct
5 Correct 5 ms 25236 KB Output is correct
6 Correct 5 ms 25424 KB Output is correct
7 Correct 4 ms 25168 KB Output is correct
8 Correct 5 ms 25168 KB Output is correct
9 Correct 6 ms 25680 KB Output is correct
10 Correct 5 ms 25168 KB Output is correct
11 Correct 13 ms 30236 KB Output is correct
12 Correct 25 ms 32676 KB Output is correct
13 Correct 46 ms 40344 KB Output is correct
14 Correct 73 ms 46816 KB Output is correct
15 Correct 88 ms 47208 KB Output is correct
16 Correct 72 ms 42392 KB Output is correct
17 Correct 68 ms 41708 KB Output is correct
18 Correct 22 ms 32468 KB Output is correct
19 Correct 72 ms 46668 KB Output is correct
20 Correct 87 ms 47200 KB Output is correct
21 Correct 65 ms 42480 KB Output is correct
22 Correct 67 ms 37112 KB Output is correct
23 Correct 85 ms 46648 KB Output is correct
24 Correct 9 ms 19280 KB Output is correct
25 Correct 12 ms 30272 KB Output is correct
26 Correct 23 ms 32672 KB Output is correct
27 Incorrect 46 ms 40224 KB Output isn't correct
28 Halted 0 ms 0 KB -