oj.uz

Submission #1104753

# Submission time Handle Problem Language Result Execution time Memory
1104753 2024-10-24T10:17:19 Z Naxocist Tropical Garden (IOI11_garden) C++17
49 / 100
 49 ms 53164 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 cycle(int u, int root) {
  if(vis[u]) return u == root;
  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;
  memset(d1, -1, sizeof d1);
  d1[p] = 0;
  dfs(p, d1);
  bool c = cycle(p, p);
  if(c) q = cnt;

  memset(d2, -1, sizeof d2);
  memset(vis, 0, sizeof vis);
  d2[p + n] = 0;
  cnt = 0;
  dfs(p + n, d2);
  bool cc = cycle(p + n, p + n);
  int qq = cnt;

  //for(int i=0; i<2*n; ++i) cout << d1[i] << ' ' ; cout << endl;
  //for(int i=0; i<2*n; ++i) cout << d2[i] << ' ' ; cout << endl;

  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) {
        if(c) ok = (k - d1[u]) % q == 0;
        else ok = k == d1[u];
      }

      if(d2[u] != -1 and d2[u] <= k) {
        if(cc) ok = (k - d2[u]) % qq == 0;
        else ok = k == d2[u];
      }
      res += ok;
    }
    answer(res);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29520 KB Output is correct
2 Correct 6 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 5 ms 29264 KB Output is correct
6 Correct 6 ms 29536 KB Output is correct
7 Correct 5 ms 29264 KB Output is correct
8 Correct 5 ms 29264 KB Output is correct
9 Correct 7 ms 29520 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29520 KB Output is correct
2 Correct 6 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 5 ms 29264 KB Output is correct
6 Correct 6 ms 29536 KB Output is correct
7 Correct 5 ms 29264 KB Output is correct
8 Correct 5 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 16 ms 32336 KB Output is correct
12 Correct 35 ms 36440 KB Output is correct
13 Incorrect 49 ms 53164 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29520 KB Output is correct
2 Correct 6 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 5 ms 29264 KB Output is correct
6 Correct 6 ms 29536 KB Output is correct
7 Correct 5 ms 29264 KB Output is correct
8 Correct 5 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 16 ms 32336 KB Output is correct
12 Correct 35 ms 36440 KB Output is correct
13 Incorrect 49 ms 53164 KB Output isn't correct
14 Halted 0 ms 0 KB -