oj.uz

답안 #37171

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37171 2017-12-22T05:24:20 Z szawinis 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
69 / 100
 3149 ms 74908 KB 
#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]);
}

Compilation message

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.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 28784 KB Output is correct
2 Correct 29 ms 28716 KB Output is correct
3 Correct 29 ms 28752 KB Output is correct
4 Correct 28 ms 28508 KB Output is correct
5 Correct 29 ms 28604 KB Output is correct
6 Correct 29 ms 28860 KB Output is correct
7 Correct 29 ms 28508 KB Output is correct
8 Correct 28 ms 28740 KB Output is correct
9 Correct 32 ms 29036 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 28784 KB Output is correct
2 Correct 29 ms 28716 KB Output is correct
3 Correct 29 ms 28752 KB Output is correct
4 Correct 28 ms 28508 KB Output is correct
5 Correct 29 ms 28604 KB Output is correct
6 Correct 29 ms 28860 KB Output is correct
7 Correct 29 ms 28508 KB Output is correct
8 Correct 28 ms 28740 KB Output is correct
9 Correct 32 ms 29036 KB Output is correct
10 Correct 29 ms 28560 KB Output is correct
11 Correct 51 ms 32532 KB Output is correct
12 Correct 85 ms 35048 KB Output is correct
13 Correct 159 ms 74908 KB Output is correct
14 Correct 245 ms 49392 KB Output is correct
15 Correct 280 ms 49956 KB Output is correct
16 Correct 320 ms 45496 KB Output is correct
17 Correct 233 ms 43068 KB Output is correct
18 Correct 92 ms 35268 KB Output is correct
19 Correct 238 ms 49448 KB Output is correct
20 Correct 282 ms 50020 KB Output is correct
21 Correct 268 ms 45112 KB Output is correct
22 Correct 218 ms 43380 KB Output is correct
23 Correct 255 ms 51452 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 28784 KB Output is correct
2 Correct 29 ms 28716 KB Output is correct
3 Correct 29 ms 28752 KB Output is correct
4 Correct 28 ms 28508 KB Output is correct
5 Correct 29 ms 28604 KB Output is correct
6 Correct 29 ms 28860 KB Output is correct
7 Correct 29 ms 28508 KB Output is correct
8 Correct 28 ms 28740 KB Output is correct
9 Correct 32 ms 29036 KB Output is correct
10 Correct 29 ms 28560 KB Output is correct
11 Correct 51 ms 32532 KB Output is correct
12 Correct 85 ms 35048 KB Output is correct
13 Correct 159 ms 74908 KB Output is correct
14 Correct 245 ms 49392 KB Output is correct
15 Correct 280 ms 49956 KB Output is correct
16 Correct 320 ms 45496 KB Output is correct
17 Correct 233 ms 43068 KB Output is correct
18 Correct 92 ms 35268 KB Output is correct
19 Correct 238 ms 49448 KB Output is correct
20 Correct 282 ms 50020 KB Output is correct
21 Correct 268 ms 45112 KB Output is correct
22 Correct 218 ms 43380 KB Output is correct
23 Correct 255 ms 51452 KB Output is correct
24 Correct 29 ms 28540 KB Output is correct
25 Correct 177 ms 32548 KB Output is correct
26 Correct 243 ms 35176 KB Output is correct
27 Correct 3005 ms 74900 KB Output is correct
28 Correct 1670 ms 49284 KB Output is correct
29 Correct 3149 ms 49784 KB Output is correct
30 Correct 2024 ms 45372 KB Output is correct
31 Correct 1521 ms 43060 KB Output is correct
32 Incorrect 95 ms 35576 KB Output isn't correct
33 Halted 0 ms 0 KB -