oj.uz

Submission #592683

# Submission time Handle Problem Language Result Execution time Memory
592683 2022-07-09T13:17:22 Z Mamedov Tropical Garden (IOI11_garden) C++17
0 / 100
 1 ms 468 KB 
#pragma GCC optimize ("O3")
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void dfs(int node, vvi &g, vi &dist, int &cycle) {
  for (int to : g[node]) {
    if (dist[to] == -1) {
      dist[to] = dist[node] + 1;
      dfs(to, g, dist, cycle);
    } else {
      cycle = dist[node] + 1;
    }
  }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  vvi minTrail(2, vi(N, -1));
  for (int i = 0; i < M; ++i) {
    for (int j = 0; j < 2; ++j) {
      int u = R[i][j];
      if (minTrail[0][u] == -1) {
        minTrail[0][u] = i;
      } else if (minTrail[1][u] == -1) {
        minTrail[1][u] = i;
      }
    }
  }
  for (int i = 0; i < N; ++i) {
    if (minTrail[1][i] == -1) {
      minTrail[1][i] = minTrail[0][i];
    }
  }

  vvi gt(2 * N);
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 2; ++j) {
      int trail = minTrail[j][i];
      int node = R[trail][0] + R[trail][1] - i;
      if (minTrail[0][node] == trail) {
        node += N;
      }
      gt[node].eb(i + j * N);
    }
  }
  vi cycle(2, 0);
  vvi dist(2, vi(2 * N, -1));
  dist[0][P] = 0;
  dfs(P, gt, dist[0], cycle[0]);
  dist[1][P + N] = 0;
  dfs(P + N, gt, dist[1], cycle[1]);

  for (int i = 0; i < Q; ++i) {
    int cnt = 0;
    for (int j = 0; j < N; ++j) {
      if (dist[0][j] == G[i] || (cycle[0] && G[i] > dist[0][j] && (G[i] - dist[0][j]) % cycle[0] == 0)) {
        ++cnt;
      } else if (dist[1][j] == G[i] || (cycle[1] && G[i] > dist[1][j] && (G[i] - dist[1][j]) % cycle[1] == 0)) {
        ++cnt;
      }
    }
    answer(cnt);
  }
}

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 1 ms 448 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 1 ms 448 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 1 ms 448 KB Output isn't correct
4 Halted 0 ms 0 KB -