#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#define pii pair<int, int>
#define F first
#define S second
#define ALL(x) x.begin(), x.end()
const int maxn = 150051;
int n, m, p, dist1[maxn * 2], dist2[maxn * 2],
// dist1 = best, dist2 = 2nd best
dist3[maxn * 2],
r[maxn * 2], cycle1 = -1, cycle2 = -1;
vector<pii> adj[maxn];
vector<int> adj2[maxn * 2];
// i * 2 = incoming is not best, leads to best
// i * 2 + 1 = incoming is best, leads to second best
map<int, vector<int>> mp1, mp2, ans1, ans2;
// make functional group
map<int, int> re;
void bfs(){
queue<int> q; q.push(p * 2); dist1[p * 2] = 0;
while (!q.empty()){
int v = q.front(); q.pop();
for (auto u : adj2[v]){
if (dist1[u] != -1) continue;
dist1[u] = dist1[v] + 1;
q.push(u);
}
}
q.push(p * 2 + 1); dist2[p * 2 + 1] = 1;
while (!q.empty()){
int v = q.front(); q.pop();
for (auto u : adj2[v]){
if (dist2[u] != -1) continue;
dist2[u] = dist2[v] + 1;
q.push(u);
}
}
}
void get_cycle(){
int v = p * 2;
fill(dist3, dist3 + n * 2, -1); dist3[p * 2] = 0;
while (true){
if (dist3[r[v]] != -1) break;
dist3[r[v]] = dist3[v] + 1;
v = r[v];
}
if (r[v] == p * 2){ // has cycle
cycle1 = dist3[v] + 1;
}
// for (int i = 0; i < n * 2; i++) cout << dist3[i * 2] << ' '; cout << endl;
v = p * 2 + 1;
fill(dist3, dist3 + n * 2, -1); dist3[p * 2 + 1] = 0;
while (true){
if (dist3[r[v]] != -1) break;
dist3[r[v]] = dist3[v] + 1;
v = r[v];
}
if (r[v] == p * 2 + 1){ // has cycle
cycle2 = dist3[v] + 1;
}
// for (int i = 0; i < n * 2; i++) cout << dist3[i * 2] << ' '; cout << endl;
}
void solve(){
for (auto &pt : ans1){
int x = pt.F;
for (auto g : pt.S){
int cnt = upper_bound(ALL(mp1[x]), g) - mp1[x].begin();
re[g] += cnt;
}
}
for (auto &pt : ans2){
int x = pt.F;
for (auto g : pt.S){
int cnt = upper_bound(ALL(mp2[x]), g) - mp2[x].begin();
re[g] += cnt;
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
n = N, m = M, p = P;
for (int i = 0; i < m; i++){
adj[R[i][0]].push_back({i, R[i][1]});
adj[R[i][1]].push_back({i, R[i][0]});
}
for (int v = 0; v < n; v++){
sort(adj[v].begin(), adj[v].end());
}
for (int v = 0; v < n; v++){
int best = adj[v][0].second;
int bests_best = adj[best][0].second;
// cout << v << ' ' << best << ' ' << adj[v].size() << endl;
if (v != bests_best){
adj2[best * 2].push_back(v * 2);
r[v * 2] = best * 2;
}
else{
adj2[best * 2 + 1].push_back(v * 2);
// adj2[v * 2 + 1].push_back(best * 2);
r[v * 2] = best * 2 + 1;
}
int second_best = adj[v][min((int)adj[v].size() - 1, 1)].second;
int second_bests_best = adj[second_best][0].second;
// cout << v << ' ' << second_best << endl;
if (v != second_bests_best){
adj2[second_best * 2].push_back(v * 2 + 1);
r[v * 2 + 1] = second_best * 2;
}
else{
adj2[second_best * 2 + 1].push_back(v * 2 + 1);
r[v * 2 + 1] = second_best * 2 + 1;
}
}
// for (int i = 0; i < n * 2; i++) cout << r[i] << ' '; cout << endl;
fill(dist1, dist1 + n * 2, -1);
fill(dist2, dist2 + n * 2, -1);
bfs();
get_cycle();
// cout << cycle1 << ' ' << cycle2 << endl;
// return;
for (int v = 0; v < n; v++){
// if (v == p) continue;
if (dist1[v * 2] != -1){
if (cycle1 == -1) mp1[dist1[v * 2]].push_back(dist1[v * 2]);
else mp1[dist1[v * 2] % cycle1].push_back(dist1[v * 2]);
}
if (dist2[v * 2] != -1){
if (cycle2 == -1) mp2[dist2[v * 2]].push_back(dist2[v * 2]);
else mp2[dist2[v * 2] % cycle2].push_back(dist2[v * 2]);
}
}
// return;
for (int i = 0; i < Q; i++){
if (cycle1 == -1) ans1[G[i]].push_back(G[i]);
else ans1[G[i] % cycle1].push_back(G[i]);
if (cycle2 == -1) ans2[G[i]].push_back(G[i]);
else ans2[G[i] % cycle2].push_back(G[i]);
}
solve();
// for (int i = 0; i < 5; i++) cout << re[i] << ' '; cout << endl;
// cout << "bruh" << endl;
for (int i = 0; i < Q; i++) {
// cout << re[G[i]] << ' '; cout << endl;
answer(re[G[i]]);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10964 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
10940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10964 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
10940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10964 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
10940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
