oj.uz

Submission #1113102

# Submission time Handle Problem Language Result Execution time Memory
1113102 2024-11-15T18:22:00 Z ortsac Tropical Garden (IOI11_garden) C++17
69 / 100
 96 ms 35192 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#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(int N, int M, int P, int R[][2], int Q, int 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 21072 KB Output is correct
2 Correct 4 ms 21240 KB Output is correct
3 Correct 4 ms 21072 KB Output is correct
4 Correct 4 ms 21072 KB Output is correct
5 Correct 4 ms 21140 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 4 ms 21072 KB Output is correct
8 Correct 4 ms 21072 KB Output is correct
9 Correct 6 ms 21328 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21072 KB Output is correct
2 Correct 4 ms 21240 KB Output is correct
3 Correct 4 ms 21072 KB Output is correct
4 Correct 4 ms 21072 KB Output is correct
5 Correct 4 ms 21140 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 4 ms 21072 KB Output is correct
8 Correct 4 ms 21072 KB Output is correct
9 Correct 6 ms 21328 KB Output is correct
10 Correct 4 ms 21072 KB Output is correct
11 Correct 12 ms 23120 KB Output is correct
12 Correct 32 ms 25112 KB Output is correct
13 Correct 44 ms 30580 KB Output is correct
14 Correct 88 ms 34496 KB Output is correct
15 Correct 93 ms 35044 KB Output is correct
16 Correct 65 ms 31068 KB Output is correct
17 Correct 58 ms 30612 KB Output is correct
18 Correct 24 ms 25168 KB Output is correct
19 Correct 77 ms 34496 KB Output is correct
20 Correct 85 ms 34376 KB Output is correct
21 Correct 68 ms 30048 KB Output is correct
22 Correct 88 ms 30644 KB Output is correct
23 Correct 96 ms 35192 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21072 KB Output is correct
2 Correct 4 ms 21240 KB Output is correct
3 Correct 4 ms 21072 KB Output is correct
4 Correct 4 ms 21072 KB Output is correct
5 Correct 4 ms 21140 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 4 ms 21072 KB Output is correct
8 Correct 4 ms 21072 KB Output is correct
9 Correct 6 ms 21328 KB Output is correct
10 Correct 4 ms 21072 KB Output is correct
11 Correct 12 ms 23120 KB Output is correct
12 Correct 32 ms 25112 KB Output is correct
13 Correct 44 ms 30580 KB Output is correct
14 Correct 88 ms 34496 KB Output is correct
15 Correct 93 ms 35044 KB Output is correct
16 Correct 65 ms 31068 KB Output is correct
17 Correct 58 ms 30612 KB Output is correct
18 Correct 24 ms 25168 KB Output is correct
19 Correct 77 ms 34496 KB Output is correct
20 Correct 85 ms 34376 KB Output is correct
21 Correct 68 ms 30048 KB Output is correct
22 Correct 88 ms 30644 KB Output is correct
23 Correct 96 ms 35192 KB Output is correct
24 Correct 5 ms 21072 KB Output is correct
25 Correct 13 ms 23376 KB Output is correct
26 Correct 23 ms 25168 KB Output is correct
27 Incorrect 54 ms 30852 KB Output isn't correct
28 Halted 0 ms 0 KB -