oj.uz

Submission #1104842

# Submission time Handle Problem Language Result Execution time Memory
1104842 2024-10-24T14:11:40 Z Naxocist Tropical Garden (IOI11_garden) C++17
100 / 100
 1875 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 == 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;
      //}

      if(d1[u] != -1 and d1[u] <= k) {
        if(q) ok = (k - d1[u]) % q == 0 or ok;
        else ok = k == d1[u] or ok;
      }
      if(d2[u] != -1 and d2[u] <= k) {
        if(qq) ok = (k - d2[u]) % qq == 0 or ok;
        else ok = k == d2[u] 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 29264 KB Output is correct
3 Correct 6 ms 29520 KB Output is correct
4 Correct 6 ms 29264 KB Output is correct
5 Correct 8 ms 29124 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 8 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 29264 KB Output is correct
3 Correct 6 ms 29520 KB Output is correct
4 Correct 6 ms 29264 KB Output is correct
5 Correct 8 ms 29124 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 8 ms 29520 KB Output is correct
10 Correct 7 ms 29264 KB Output is correct
11 Correct 16 ms 32484 KB Output is correct
12 Correct 40 ms 36168 KB Output is correct
13 Correct 73 ms 52708 KB Output is correct
14 Correct 87 ms 49740 KB Output is correct
15 Correct 96 ms 48968 KB Output is correct
16 Correct 80 ms 44104 KB Output is correct
17 Correct 69 ms 42824 KB Output is correct
18 Correct 41 ms 36812 KB Output is correct
19 Correct 92 ms 49172 KB Output is correct
20 Correct 123 ms 49736 KB Output is correct
21 Correct 75 ms 44688 KB Output is correct
22 Correct 66 ms 42568 KB Output is correct
23 Correct 104 ms 51528 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 29264 KB Output is correct
3 Correct 6 ms 29520 KB Output is correct
4 Correct 6 ms 29264 KB Output is correct
5 Correct 8 ms 29124 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 8 ms 29520 KB Output is correct
10 Correct 7 ms 29264 KB Output is correct
11 Correct 16 ms 32484 KB Output is correct
12 Correct 40 ms 36168 KB Output is correct
13 Correct 73 ms 52708 KB Output is correct
14 Correct 87 ms 49740 KB Output is correct
15 Correct 96 ms 48968 KB Output is correct
16 Correct 80 ms 44104 KB Output is correct
17 Correct 69 ms 42824 KB Output is correct
18 Correct 41 ms 36812 KB Output is correct
19 Correct 92 ms 49172 KB Output is correct
20 Correct 123 ms 49736 KB Output is correct
21 Correct 75 ms 44688 KB Output is correct
22 Correct 66 ms 42568 KB Output is correct
23 Correct 104 ms 51528 KB Output is correct
24 Correct 6 ms 29264 KB Output is correct
25 Correct 80 ms 32336 KB Output is correct
26 Correct 120 ms 36168 KB Output is correct
27 Correct 825 ms 52712 KB Output is correct
28 Correct 894 ms 48788 KB Output is correct
29 Correct 880 ms 49040 KB Output is correct
30 Correct 500 ms 43756 KB Output is correct
31 Correct 482 ms 41800 KB Output is correct
32 Correct 128 ms 36176 KB Output is correct
33 Correct 837 ms 48580 KB Output is correct
34 Correct 696 ms 48968 KB Output is correct
35 Correct 447 ms 43640 KB Output is correct
36 Correct 1145 ms 41848 KB Output is correct
37 Correct 669 ms 50660 KB Output is correct
38 Correct 1875 ms 61908 KB Output is correct