Submission #1104666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104666		Naxocist	Tropical Garden (IOI11_garden)	C++17	0 / 100	7 ms	27472 KiB

garden

#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 dist[2*N];
int n, m, p;

bitset<2*N> vis;
int cycle(int u, int par, int d) {
  if(vis[u]) return d;
  vis[u] = true;

  for(auto v : adj[u]) {
    if(v == par) continue ;
    int d = cycle(v, u, d + 1);
    if(d > 1) return d;
  }

  return 1;
}

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

// 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]) {
      //cout << u << ' ' << v << endl;
      rev[v].pb(u);
    }
  }

  int q = cycle(p,-1, 1);
  //cout << "q : " << q << endl;
  memset(dist, -1, sizeof dist);
  vis.reset(); 
  vis[p] = true;

  dist[p] = 0;
  dfs(p);
  dist[p + n] = 0;
  dfs(p + n);

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

  for(int i=0; i<Q; ++i) {
    int k = G[i], res = 0;
    for(int u=0; u<n; ++u) {
      if(dist[u] == -1 or dist[u] < k) continue;
      if((dist[u] - k) % q == 0) {
        res ++;
      } 
    }
    answer(res);
  }
}

Compilation message (stderr)

garden.cpp: In function 'int cycle(int, int, int)':
garden.cpp:23:18: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |     int d = cycle(v, u, d + 1);
      |             ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31