oj.uz

Submission #1104844

# Submission time Handle Problem Language Result Execution time Memory
1104844 2024-10-24T14:13:26 Z Naxocist Tropical Garden (IOI11_garden) C++17
100 / 100
 1766 ms 61908 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

#define pb emplace_back
#define INF 2e9

const int N = 2e5 + 3;
vector<int> adj[N];
int mx[N], mx2[N];
vector<int> g[2*N], rev[2*N];
int d1[2*N], d2[2*N];
bool vis[2*N];
int n, m, p;

int cnt = 0;
bool ok = false;
bool cycle(int u, int root) {
  if(vis[u]) {
    ok = u == root;
    return true;
  }
  cnt ++;
  vis[u] = true;

  for(auto v : g[u]) {
    bool t = cycle(v, root);
    if(t) return true;
  }
  return false;
}

void dfs(int u, int d[]) {
  for(auto v : rev[u]) {
    if(d[v] != -1 and d[u] + 1 >= d[v]) continue ;
    d[v] = d[u] + 1;
    dfs(v, d);
  }
}

// answer (x);
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  n = N, m = M, p = P;
  memset(mx, -1, sizeof mx);
  memset(mx2, -1, sizeof mx2);
  for(int i=0; i<m; ++i) {
    int u = R[i][0], v = R[i][1];

    if(mx[u] == -1) mx[u] = v;
    else if(mx2[u] == -1) mx2[u] = v;

    if(mx[v] == -1) mx[v] = u;
    else if(mx2[v] == -1) mx2[v] = u;

    adj[u].pb(v), adj[v].pb(u);
  }

  for(int u=0; u<2*n; ++u) {
    if(u < n) {
      // didn't walk through beautiful edge before u
      if(mx[u] == -1) continue ;

      int v = mx[u];
      if(mx[v] == u) v += n;
      g[u].pb(v);
    }else {
      // walked through beautiful edge already before u
      int v = mx2[u - n];
      if(v == -1) v = mx[u - n];
      if(v == -1) continue ;
      if(mx[v] == u - n) v += n;
      g[u].pb(v);
    }
  }

  for(int u=0; u<2*n; ++u) {
    for(int v : g[u]) {
      rev[v].pb(u);
    }
  }

  int q = 0, qq = 0;
  memset(d1, -1, sizeof d1);
  d1[p] = 0;
  dfs(p, d1);
  cycle(p, p);
  if(ok) q = cnt;

  memset(d2, -1, sizeof d2);
  memset(vis, 0, sizeof vis);
  d2[p + n] = 0;
  cnt = 0;
  ok = false;
  dfs(p + n, d2);
  cycle(p + n, p + n);
  if(ok) qq = cnt;

  for(int i=0; i<Q; ++i) {
    int k = G[i], res = 0;
    for(int u=0; u<n; ++u) {
      bool ok = false;
      if(d1[u] != -1 and d1[u] <= k) {
        int len = k - d1[u];
        if(q) ok = len%q==0;
        else ok = len == 0;
      }
      if(d2[u] != -1 and d2[u] <= k) {
        int len = k - d2[u];
        if(qq) ok = len%qq==0 or ok;
        else ok = len == 0 or ok;
      }

      res += ok;
    }
    answer(res);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29520 KB Output is correct
2 Correct 5 ms 29360 KB Output is correct
3 Correct 5 ms 29520 KB Output is correct
4 Correct 5 ms 29360 KB Output is correct
5 Correct 5 ms 29432 KB Output is correct
6 Correct 5 ms 29520 KB Output is correct
7 Correct 5 ms 29264 KB Output is correct
8 Correct 5 ms 29388 KB Output is correct
9 Correct 6 ms 29520 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29520 KB Output is correct
2 Correct 5 ms 29360 KB Output is correct
3 Correct 5 ms 29520 KB Output is correct
4 Correct 5 ms 29360 KB Output is correct
5 Correct 5 ms 29432 KB Output is correct
6 Correct 5 ms 29520 KB Output is correct
7 Correct 5 ms 29264 KB Output is correct
8 Correct 5 ms 29388 KB Output is correct
9 Correct 6 ms 29520 KB Output is correct
10 Correct 5 ms 29264 KB Output is correct
11 Correct 13 ms 32480 KB Output is correct
12 Correct 24 ms 36184 KB Output is correct
13 Correct 46 ms 52552 KB Output is correct
14 Correct 71 ms 48712 KB Output is correct
15 Correct 85 ms 48968 KB Output is correct
16 Correct 61 ms 43592 KB Output is correct
17 Correct 57 ms 41740 KB Output is correct
18 Correct 29 ms 36168 KB Output is correct
19 Correct 82 ms 48784 KB Output is correct
20 Correct 92 ms 48968 KB Output is correct
21 Correct 72 ms 43592 KB Output is correct
22 Correct 66 ms 41696 KB Output is correct
23 Correct 84 ms 50504 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29520 KB Output is correct
2 Correct 5 ms 29360 KB Output is correct
3 Correct 5 ms 29520 KB Output is correct
4 Correct 5 ms 29360 KB Output is correct
5 Correct 5 ms 29432 KB Output is correct
6 Correct 5 ms 29520 KB Output is correct
7 Correct 5 ms 29264 KB Output is correct
8 Correct 5 ms 29388 KB Output is correct
9 Correct 6 ms 29520 KB Output is correct
10 Correct 5 ms 29264 KB Output is correct
11 Correct 13 ms 32480 KB Output is correct
12 Correct 24 ms 36184 KB Output is correct
13 Correct 46 ms 52552 KB Output is correct
14 Correct 71 ms 48712 KB Output is correct
15 Correct 85 ms 48968 KB Output is correct
16 Correct 61 ms 43592 KB Output is correct
17 Correct 57 ms 41740 KB Output is correct
18 Correct 29 ms 36168 KB Output is correct
19 Correct 82 ms 48784 KB Output is correct
20 Correct 92 ms 48968 KB Output is correct
21 Correct 72 ms 43592 KB Output is correct
22 Correct 66 ms 41696 KB Output is correct
23 Correct 84 ms 50504 KB Output is correct
24 Correct 6 ms 29264 KB Output is correct
25 Correct 81 ms 32448 KB Output is correct
26 Correct 124 ms 36372 KB Output is correct
27 Correct 773 ms 52716 KB Output is correct
28 Correct 826 ms 48788 KB Output is correct
29 Correct 798 ms 48968 KB Output is correct
30 Correct 530 ms 43592 KB Output is correct
31 Correct 458 ms 41604 KB Output is correct
32 Correct 125 ms 36176 KB Output is correct
33 Correct 877 ms 48616 KB Output is correct
34 Correct 759 ms 49020 KB Output is correct
35 Correct 459 ms 43644 KB Output is correct
36 Correct 1047 ms 41848 KB Output is correct
37 Correct 640 ms 50504 KB Output is correct
38 Correct 1766 ms 61908 KB Output is correct