oj.uz

Submission #1104837

# Submission time Handle Problem Language Result Execution time Memory
1104837 2024-10-24T14:07:48 Z Naxocist Tropical Garden (IOI11_garden) C++17
100 / 100
 1842 ms 63768 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 == 0 and len == 0) ok = true;
        else if(q != 0 and len%q==0) ok = true;
      }
      if(d2[u] != -1 and d2[u] <= k) {
        int len = k - d2[u];
        if(qq == 0 and len == 0) ok = true;
        else if(qq != 0 and len%qq==0) ok = true;
      }
      res += ok;
    }
    answer(res);
  }
}

Subtask #1
49.0 / 49.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29400 KB Output is correct
2 Correct 5 ms 29432 KB Output is correct
3 Correct 6 ms 29520 KB Output is correct
4 Correct 6 ms 29264 KB Output is correct
5 Correct 7 ms 29264 KB Output is correct
6 Correct 7 ms 29520 KB Output is correct
7 Correct 5 ms 29264 KB Output is correct
8 Correct 6 ms 29264 KB Output is correct
9 Correct 7 ms 29520 KB Output is correct
10 Correct 5 ms 29264 KB Output is correct
11 Correct 17 ms 32348 KB Output is correct
12 Correct 29 ms 36412 KB Output is correct
13 Correct 54 ms 53064 KB Output is correct
14 Correct 75 ms 49900 KB Output is correct
15 Correct 90 ms 48968 KB Output is correct
16 Correct 70 ms 44360 KB Output is correct
17 Correct 65 ms 43080 KB Output is correct
18 Correct 28 ms 36604 KB Output is correct
19 Correct 81 ms 48968 KB Output is correct
20 Correct 91 ms 49748 KB Output is correct
21 Correct 101 ms 44872 KB Output is correct
22 Correct 72 ms 42776 KB Output is correct
23 Correct 85 ms 52180 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29400 KB Output is correct
2 Correct 5 ms 29432 KB Output is correct
3 Correct 6 ms 29520 KB Output is correct
4 Correct 6 ms 29264 KB Output is correct
5 Correct 7 ms 29264 KB Output is correct
6 Correct 7 ms 29520 KB Output is correct
7 Correct 5 ms 29264 KB Output is correct
8 Correct 6 ms 29264 KB Output is correct
9 Correct 7 ms 29520 KB Output is correct
10 Correct 5 ms 29264 KB Output is correct
11 Correct 17 ms 32348 KB Output is correct
12 Correct 29 ms 36412 KB Output is correct
13 Correct 54 ms 53064 KB Output is correct
14 Correct 75 ms 49900 KB Output is correct
15 Correct 90 ms 48968 KB Output is correct
16 Correct 70 ms 44360 KB Output is correct
17 Correct 65 ms 43080 KB Output is correct
18 Correct 28 ms 36604 KB Output is correct
19 Correct 81 ms 48968 KB Output is correct
20 Correct 91 ms 49748 KB Output is correct
21 Correct 101 ms 44872 KB Output is correct
22 Correct 72 ms 42776 KB Output is correct
23 Correct 85 ms 52180 KB Output is correct
24 Correct 7 ms 29180 KB Output is correct
25 Correct 78 ms 32592 KB Output is correct
26 Correct 157 ms 36424 KB Output is correct
27 Correct 798 ms 53572 KB Output is correct
28 Correct 864 ms 50388 KB Output is correct
29 Correct 810 ms 50760 KB Output is correct
30 Correct 544 ms 45324 KB Output is correct
31 Correct 498 ms 43400 KB Output is correct
32 Correct 121 ms 36948 KB Output is correct
33 Correct 830 ms 50384 KB Output is correct
34 Correct 766 ms 50788 KB Output is correct
35 Correct 467 ms 45216 KB Output is correct
36 Correct 1060 ms 43592 KB Output is correct
37 Correct 647 ms 52556 KB Output is correct
38 Correct 1842 ms 63768 KB Output is correct