oj.uz

Submission #1104813

# Submission time Handle Problem Language Result Execution time Memory
1104813 2024-10-24T13:37:36 Z Naxocist Tropical Garden (IOI11_garden) C++17
0 / 100
 7 ms 29520 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 : rev[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, qq;
  memset(d1, -1, sizeof d1);
  d1[p] = 0;
  dfs(p, d1);
  cycle(p, p);
  if(ok) q = cnt;
  bool c = ok;

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

  //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
0 / 49.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 31.0

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