#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
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);
~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
28640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
28640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
28640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
