Submission #37169

#	Time	Username	Problem	Language	Result	Execution time	Memory
37169		szawinis	Tropical Garden (IOI11_garden)	C++14	0 / 100	30 ms	28604 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <tuple>
using namespace std;
const int N = 3e5 + 1, INF = 1e9+1;

int n, p, q, pidx, pdepth, res[N];
vector<int> g[N], gt[N], cycle, cnt[N]; // use idx in cycle
vector<pair<int, int>> init_g[N];
bool oncycle[N];

int mark[N];
stack<int> st;
void dfs_cycle(int u, int par) {
  // cout << u << ' ' << par << endl;
  mark[u] = 1;
  st.push(u);
  for(int v: g[u]) if(v != par) {
    if(!mark[v]) dfs_cycle(v, u);
    else if(mark[v] == 1) {
      // cout << v << endl;
      stack<int> tmp;
      while(st.top() != v) {
        cycle.push_back(st.top());
        oncycle[st.top()] = true;
        tmp.push(st.top());
        st.pop();
      }
      cycle.push_back(v);
      oncycle[v] = true;
      reverse(cycle.begin(), cycle.end());
      while(!tmp.empty()) st.push(tmp.top()), tmp.pop();
    }
  }
  st.pop();
  mark[u] = 2;
} 

void bfs_tree(int src, int cycle_idx, int targ) {
  queue<tuple<int,int,int>> q;
  q.emplace(src, -1, 0);
  while(!q.empty()) {
    int u, par, d; tie(u, par, d) = q.front();
    q.pop();
    // cout << cycle_idx << ' ' << u << ' ' << d << endl;
    if(u < n) {
      if(cnt[cycle_idx].size() < d+1) cnt[cycle_idx].resize(d+1);
      ++cnt[cycle_idx][d];
    }
    if(u == targ) {
      pidx = cycle_idx;
      pdepth = d;
    }
    for(int v: gt[u]) if(v != par && !oncycle[v]) // transpose
      q.emplace(v, u, d+1);
  }
}

void calc(int tp) {
  fill(mark, mark+2*n, 0);
  fill(oncycle, oncycle+2*n, 0);
  for(int i = 0; i < cycle.size(); i++) cnt[i].clear();
  cycle.clear();

  dfs_cycle(p + tp * n, -1);
  // for(int i = 0; i < cycle.size(); i++) cout << cycle[i] << ' ';
  // cout << endl;
  for(int i = 0; i < cycle.size(); i++) bfs_tree(cycle[i], i, p + tp * n);
}

int solve(int tp, int len) {
  if(!pdepth) {
    int ret = 0;
    for(int i = 0; i < cycle.size(); i++) {
      int cycle_dist = (pidx + cycle.size() - i) % cycle.size();
      int targ = (len - cycle_dist) % (int) cycle.size();  // must be cast or else will be unsigned
      // cout << i << ' ' << targ << ' ' << len - cycle_dist << endl;
      ret += (targ < cnt[i].size() ? cnt[i][targ] : 0);
    }
    return ret;
  } else return (len + pdepth < cnt[pidx].size() ? cnt[pidx][len + pdepth] : 0);
}

void count_routes(int _n, int m, int _p, int _e[][2], int _q, int len[]) {
  n = _n, p = _p, q = _q;
  for(int i = 0; i < m; i++) {
    init_g[_e[i][0]].emplace_back(_e[i][1], i);
    init_g[_e[i][1]].emplace_back(_e[i][0], i);
  }
  for(int u = 0; u < n; u++) {
    for(int i = 0, v, idx; i < min((int)init_g[u].size(), 2); i++) {
      tie(v, idx) = init_g[u][i];
      g[u + i * n].push_back(v + (init_g[v].size() > 1 && idx == init_g[v][0].second) * n);
      // cout << u + i * n << ' ' << v + (init_g[v].size() > 1 && idx == init_g[v][0].second) * n << endl;
      gt[v + (init_g[v].size() > 1 && idx == init_g[v][0].second) * n].push_back(u + i * n);
    }
  }
  calc(0);
  //for(int i = 0; i < q; i++) res[i] += solve(0, len[i]);
  // cout << res[0] << endl;
  calc(1);
  //for(int i = 0; i < q; i++) res[i] += solve(1, len[i]);
  // cout << res[0] << endl;
  for(int i = 0; i < q; i++) answer(res[i]);
}

Compilation message (stderr)

garden.cpp: In function 'void bfs_tree(int, int, int)':
garden.cpp:54:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(cnt[cycle_idx].size() < d+1) cnt[cycle_idx].resize(d+1);
          ~~~~~~~~~~~~~~~~~~~~~~^~~~~
garden.cpp: In function 'void calc(int)':
garden.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < cycle.size(); i++) cnt[i].clear();
                  ~~^~~~~~~~~~~~~~
garden.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < cycle.size(); i++) bfs_tree(cycle[i], i, p + tp * n);
                  ~~^~~~~~~~~~~~~~
garden.cpp: In function 'int solve(int, int)':
garden.cpp:81:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < cycle.size(); i++) {
                    ~~^~~~~~~~~~~~~~
garden.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       ret += (targ < cnt[i].size() ? cnt[i][targ] : 0);
               ~~~~~^~~~~~~~~~~~~~~
garden.cpp:88:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   } else return (len + pdepth < cnt[pidx].size() ? cnt[pidx][len + pdepth] : 0);
                  ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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