Submission #348099

#	Time	Username	Problem	Language	Result	Execution time	Memory
348099		milleniumEeee	Tropical Garden (IOI11_garden)	C++17	49 / 100	89 ms	52668 KiB

garden

/*
ребра как вершины
*/
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
clock_t start;
#define pii pair<int, int>
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;
 
const int MAXN = 150005;
int n, m, q, p;
 
//__________________
vector <pii> edges;
vector <pii> g[MAXN];
map <pii, int> mp;
vector <int> eg[MAXN * 2]; // edge graph
vector <int> reg[MAXN * 2];
pii from_to[MAXN * 2];
int mn1, mn2;
vector <int> pr, siz;
vector <int> lst;
vector <bool> cycle;
vector <int> used;
int tiktak = 0;
vector <int> tin, tout;
vector <int> cycle_root;
vector <int> dist;
vector <int> cycle_size;
vector <vector<int>> mn_dist;
//__________________

int findp(int v) {
  if (v == pr[v]) {
    return v;
  }
  return pr[v] = findp(pr[v]);
}
void unite(int a, int b) {
  a = findp(a);
  b = findp(b);
  if (a == b) {
    return;
  }
  if (siz[a] > siz[b]) {
    swap(a, b);
  }
  pr[a] = b;
  siz[b] += siz[a];
}
bool find_cycle(int v) {
  used[v] = 1;
  for (int to : eg[v]) {
    if (!used[to]) {
      lst[to] = v;
      bool f = find_cycle(to);
      if (f) {
        return true;          
      }
    }
    if (used[to] == 1) {
      int fn = v;
      while (fn != to) {
        cycle[fn] = true;
        fn = lst[fn];
      }
      cycle[to] = true;
      return true;
    }
  }
  used[v] = 2;
  return false;
}
void rev_dfs(int v, int root, int len = 0) {
  tin[v] = ++tiktak;
  cycle_root[v] = root;
  dist[v] = len;
  for (int to : reg[v]) {
    if (!cycle[to]) {
      rev_dfs(to, root, len + 1);
    }
  }
  tout[v] = tiktak;
}
void cycle_dfs(int v, int type, int len = 0) {
  mn_dist[type][v] = len;
  for (int to : eg[v]) {
    if (mn_dist[type][to] == -1) {
      cycle_dfs(to, type, len + 1);
    }
  }
}
bool father(int a, int b) {
  return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}
void calc(vector <int> comp) {
  find_cycle(comp[0]);
  int CYCLE_SIZE = 0;
  for (int el : comp) {
    if (cycle[el]) {
      rev_dfs(el, el);
      CYCLE_SIZE++;
    }
  }
  for (int el : comp) {
    cycle_size[el] = CYCLE_SIZE;
  }
  cycle_dfs(mn1, 1);
  cycle_dfs(mn2, 2);
  for (int type = 1; type <= 2; type++) {
    for (int el : comp) {
      if (cycle[el]) {
        mn_dist[type][el] = (cycle_size[el] - mn_dist[type][el]) % cycle_size[el];
        assert(mn_dist[type][el] < cycle_size[el]);
      }
    }
  }
}
bool ok(int v, int k) {
  if (!cycle[mn1]) {
    if (father(mn1, v)) {
      int up = dist[mn1];
      int down = dist[v];
      if (down - up == k) {
        exit(0);
        return true;
      }
    }
  } else if (pr[v] == pr[mn1]) {
    int h = dist[v];
    int my_root = cycle_root[v];
    if (k >= h + mn_dist[1][my_root] && (k - h - mn_dist[1][my_root]) % cycle_size[my_root] == 0) {
      return true;
    }
  }
  if (!cycle[mn2]) {
    if (father(mn2, v)) {
      int up = dist[mn2];
      int down = dist[v];
      if (down - up == k) {
        return true;
      }
    }
  } else if (pr[v] == pr[mn2]) {
    int h = dist[v];
    int my_root = cycle_root[v];
    if (k >= h + mn_dist[2][my_root] && (k - h - mn_dist[2][my_root]) % cycle_size[my_root] == 0) {
      return true;
    }
  }
  return false;
}
void precalc(int sz) {
  mn1 = g[p][0].sc;
  if (szof(g[p]) > 1) {
    mn2 = g[p][1].sc;
  } else {
    mn2 = mn1;
  }
  mn_dist.resize(3);
  for (int i = 1; i <= 2; i++) {
    mn_dist[i].resize(sz, -1);
  }
  cycle_size.resize(sz);
  dist.resize(sz);
  cycle_root.resize(sz);
  pr.resize(sz);
  siz.resize(sz);
  lst.resize(sz);
  used.resize(sz, 0);
  cycle.resize(sz, false);
  tin.resize(sz);
  tout.resize(sz);
  for (int i = 0; i < sz; i++) {
    pr[i] = i;
    siz[i] = 1;
    lst[i] = -1;
  }
  for (int i = 0; i < sz; i++) {
    for (int to : eg[i]) {
      unite(i, to);
      reg[to].pb(i);
    }
  }
  vector <pii> vec;
  for (int i = 0; i < sz; i++) {
    vec.pb({findp(i), i});
  }
  sort(all(vec));
  for (int i = 0; i < sz; i++) {
    int r = i;
    while (r < sz && vec[r].fr == vec[i].fr) {
      r++;
    }r--;
    vector <int> comp;
    for (int j = i; j <= r; j++) {
      comp.pb(vec[j].sc);
    }
    calc(comp);
    i = r;
  }
}

pii para(int pos) {
  int x = from_to[pos].fr, y = from_to[pos].sc;
  pii res = {min(x, y), max(x, y)};
  return res;
}
 
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  start = clock();
  n = N;
  m = M;
  q = Q;
  p = P;
  for (int i = 0; i < m; i++) {
    int x = R[i][0];
    int y = R[i][1];
    edges.pb({x, y});
    if (szof(g[x]) < 2) {
      g[x].pb({y, i});
    }
    if (szof(g[y]) < 2) {
      g[y].pb({x, i});
    }
  }
  int cnt = 0;
  for (int v = 0; v < n; v++) {
    for (auto &edge : g[v]) {
      int to = edge.fr, ind = edge.sc;
      mp[{v, to}] = cnt++;
      from_to[cnt - 1] = {v, to};
      edge.sc = cnt - 1;
    }
  }
  int sz = 0;
  for (int v = 0; v < n; v++) {
    for (auto edge : g[v]) {
      sz++;
      int to = edge.fr, ind = edge.sc;
      if (szof(g[to]) == 1) {
        eg[ind].pb(mp[{to, v}]);
        continue;
      }
      pii cur = para(ind);
      pii mn1 = para(mp[{to, g[to][0].fr}]);
      pii mn2 = para(mp[{to, g[to][1].fr}]);  
      if (cur != mn1) {
        eg[ind].pb(mp[{to, g[to][0].fr}]);
      } else {
        eg[ind].pb(mp[{to, g[to][1].fr}]);
      }
    }
  }
  precalc(sz);
  
  int t = clock() - start;
  if (t > 4000) {
    assert(false);
  }
  //dasdasdsadadsaldksakokjdosaihdujahiduhasiudhsahdijujsahdiuashgdihsagdijsahdisahdhsaijdhas
  
  int ans;
  for (int i = 0; i < q; i++) {
    ans = 0;
    for (int v = 0; v < n; v++) { // не забыть
      int V = g[v][0].sc, k = G[i];
      if (!cycle[mn1]) {
        if (father(mn1, V)) {
          int up = dist[mn1];
          int down = dist[V];
          if (down - up == k) {
            ans++;
            continue;
          }
        }
      } else if (pr[V] == pr[mn1]) {
        int h = dist[V];
        int my_root = cycle_root[V];
        if (k >= h + mn_dist[1][my_root] && (k - h - mn_dist[1][my_root]) % cycle_size[my_root] == 0) {
          ans++;
          continue;
        }
      }
      if (!cycle[mn2]) {
        if (father(mn2, V)) {
          int up = dist[mn2];
          int down = dist[V];
          if (down - up == k) {
            ans++;
            continue;
          }
        }
      } else if (pr[V] == pr[mn2]) {
        int h = dist[V];
        int my_root = cycle_root[V];
        if (k >= h + mn_dist[2][my_root] && (k - h - mn_dist[2][my_root]) % cycle_size[my_root] == 0) {
          ans++;
          continue;
        }
      }
    }
    answer(ans);
  }
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:238:25: warning: unused variable 'ind' [-Wunused-variable]
  238 |       int to = edge.fr, ind = edge.sc;
      |                         ^~~
garden.cpp:255:11: warning: variable 'mn2' set but not used [-Wunused-but-set-variable]
  255 |       pii mn2 = para(mp[{to, g[to][1].fr}]);
      |           ^~~

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