제출 #37171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
37171		szawinis	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	69 / 100	3149 ms	74908 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>
#include <cassert>
using namespace std;
const int N = 3e5 + 1, INF = 1e9+1;

int n, p, q, res[N], cycle_idx[N], d[N];
vector<int> g[N], gt[N], cycle, cnt[N];
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 dfs_tree(int u, int par) {
  if(u < n) {
    if (cnt[cycle_idx[u]].size() < d[u]+1)
      cnt[cycle_idx[u]].resize(d[u] + 1);
    ++cnt[cycle_idx[u]][d[u]];
  }
  for(int v: gt[u]) if(v != par && !oncycle[v]) {
    d[v] = d[u] + 1;
    cycle_idx[v] = cycle_idx[u];
    dfs_tree(v, u);
  }
}

void calc() {
  fill(mark, mark+2*n, 0);
  fill(oncycle, oncycle+2*n, 0);
  fill(cycle_idx, cycle_idx+2*n, -1);
  cycle.clear();

  dfs_cycle(p, -1);
  // for(int i = 0; i < cycle.size(); i++) cout << cycle[i] << ' ';
  // cout << endl;
  for(int i = 0; i < cycle.size(); i++) {
    cycle_idx[cycle[i]] = i;
    dfs_tree(cycle[i], cycle[i]);
  }
}

int solve(int len) {
  if(d[p]) {
    return (len + d[p] < cnt[cycle_idx[p]].size()
                ? cnt[cycle_idx[p]][len + d[p]]
                : 0);
  }
  // assume !d[p]
  int ret = 0;
  for(int i = 0; i < n; i++) if(cycle_idx[i] != -1) { // only consider (i, 0)
    int sz = cycle.size();
    int cycle_dist = (cycle_idx[p] + sz - cycle_idx[i]) % sz;
    // cout << i << ' ' << cycle_dist << ' ' << (len - d[i] - cycle_dist) % sz << endl;
    ret += d[i] + cycle_dist <= len && !((len - d[i] - cycle_dist) % sz);
  }
  return ret;
}

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();
  for(int i = 0; i < q; i++) res[i] += solve(len[i]);
  // cout << res[0] << endl;
  p += n;
  calc();
  for(int i = 0; i < q; i++) res[i] += solve(len[i]);
  // cout << res[0] << endl;
  for(int i = 0; i < q; i++) answer(res[i]);
}

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'void dfs_tree(int, int)':
garden.cpp:49:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (cnt[cycle_idx[u]].size() < d[u]+1)
         ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
garden.cpp: In function 'void calc()':
garden.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < cycle.size(); i++) {
                  ~~^~~~~~~~~~~~~~
garden.cpp: In function 'int solve(int)':
garden.cpp:77:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return (len + d[p] < cnt[cycle_idx[p]].size()
             ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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