Submission #348215

#	Time	Username	Problem	Language	Result	Execution time	Memory
348215		milleniumEeee	Tropical Garden (IOI11_garden)	C++14	69 / 100	5061 ms	63840 KiB

garden

/*
ребра как вершины
*/
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#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];
vector <int> eg[MAXN * 2]; // edge graph
vector <int> reg[MAXN * 2];
pii from_to[MAXN * 2];
int mn1, mn2;
int pr[MAXN * 2], siz[MAXN * 2];
int lst[MAXN * 2];
bool cycle[MAXN * 2];
vector <int> used(MAXN * 2, false);
int tiktak = 0;
int tin[MAXN * 2], tout[MAXN * 2];
int cycle_root[MAXN * 2];
int dist[MAXN * 2];
int cycle_size[MAXN * 2];
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) {
  if (pr[comp[0]] != pr[mn1] && pr[comp[2]] != pr[mn2]) {
    return;
  }
  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);
  }
  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 <int> comp[MAXN * 2];
  for (int i = 0; i < sz; i++) {
    comp[findp(i)].pb(i);
  }
  for (int i = 0; i < sz; i++) {
    if (!comp[i].empty()) {
      calc(comp[i]);      
    }
  }
}

int tp;
bool get(int v, int fn, int k) {
  if (pr[v] != pr[fn]) {
    return 0;
  }
  if (cycle[v] && !cycle[fn]) {
    return 0;
  }
  
  if (!cycle[fn]) {
    if (tin[fn] <= tin[v] && tout[v] <= tout[fn] && dist[v] - dist[fn] == k) {
      return 1;
    } else {
      return 0;
    }
  } else {
    tp = (fn == mn1 ? 1 : 2);
    if (k - dist[v] - mn_dist[tp][cycle_root[v]] >= 0 &&
    (k - dist[v] - mn_dist[tp][cycle_root[v]]) % cycle_size[cycle_root[v]] == 0) {
      return 1;
    } else {
      return 0;
    }
  }
}
 
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  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;
      from_to[cnt] = {v, to};
      edge.sc = cnt;
      cnt++;
    }
  }
  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(g[to][0].sc);
        continue;
      }
      int cur = edge.sc;
      int mn1 = g[to][0].sc;
      int mn2 = g[to][1].sc; 
      int x = from_to[cur].fr, y = from_to[cur].sc;
      int xx = from_to[mn1].fr, yy = from_to[mn1].sc;
      if (x > y) {
        swap(x, y);
      } 
      if (xx > yy) {
        swap(xx, yy);
      }
      if (!(x == xx && y == yy)) {
        eg[ind].pb(mn1);
      } else {
        eg[ind].pb(mn2);
      }
    }
  }
  precalc(sz);
  int ans;
  
  //assert(n != 150000 || m != 150000);
  
  for (int i = 0; i < q; i++) {
    ans = 0;
    bool ok;
    for (int v = 0; v < n; v++) {
      ok = get(g[v][0].sc, mn1, G[i]);
      ok |= get(g[v][0].sc, mn2, G[i]);
      ans += ok;
    }
    answer(ans);
  }
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:240:25: warning: unused variable 'ind' [-Wunused-variable]
  240 |       int to = edge.fr, ind = edge.sc;
      |                         ^~~

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