#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
/*
só interessam as duas arestas mais valiosas de um cara
ou vc ta em um ciclo ou vc escoa um ciclo
*/
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;
const int MAXN = 150000+10, MAXQ = 2e3+10, BIG = 1e9+1;
vector<pii> e[MAXN];
int ds[MAXN][2]; // distância até p
bool st[MAXN][2]; // o estado que pega p
bool dfs(int x, int l, int P){
bool cr = 0;
if (e[x].size() > 1 && l == e[x][0].second) cr=1;
if (ds[x][cr] != BIG) return cr;
ds[x][cr] = -1;
auto i = e[x][cr].first;
if (i == P){
ds[x][cr] = 1, st[x][cr] = (e[i].size()>1 && e[x][cr].second==e[i][0].second);
return cr;
}
bool is = dfs(i, e[x][cr].second, P);
if (ds[i][is] != -1){
ds[x][cr] = ds[i][is]+1;
st[x][cr] = st[i][is];
}
return cr;
}
void count_routes(int n, int m, int P, int R[][2], int q, int G[]){
for (int i=0;i<n;i++){
e[i].clear();
ds[i][0] = ds[i][1] = BIG;
}
for (int i=0;i<m;i++){
int a = R[i][0], b = R[i][1];
if (e[a].size()<2) e[a].emplace_back(b, i);
if (e[b].size()<2) e[b].emplace_back(a, i);
}
for (int i=0;i<n;i++){
if (ds[i][0] == BIG) dfs(i, -1, P);
}
if(!e[P].empty()) dfs(P, e[P][0].second, P);
// for (int i=0;i<n;i++) cerr << ds[i][0] << ' ' << ds[i][1] << '\n';
for (int _=0;_<q;_++){
int sk = G[_], cr = 0;
for (int i=0;i<n;i++) if (ds[i][0] != -1 && ds[i][0]<=sk){
int k = sk;
long long d = ds[i][0];
if (d==k){
cr++;
// cerr << i << " can\n";
continue;
}
k-=d;
vector<int> vi(2, -1);
long long ex=0, cy=0;
bool cst = st[i][0];
vi[cst]=0;
while (1){
ex+=ds[P][cst];
if (ex==k) break;
cst = st[P][cst];
if (vi[cst] != -1){
cy = ex-vi[cst];
break;
}
vi[cst] = ex;
}
if(ex>k) continue;
if (ex==k || st[P][cst] == cst){ // ciclo de uma parte ou interrompido
if ((k-ex)%cy == 0){
cr++;
// cerr << i << " can\n";
}
}else{ // ciclo de duas partes
long long psm = ds[P][cst];
int v = (k-ex)%cy;
if (v == 0 || v==psm){
cr++; // ciclo todo ou finaliza no pequeno
// cerr << i << " can\n";
}
// if (i==4) cerr << k << ' ' << cst << ' ' << ex << ' ' << cy << ' ' << psm << '\n';
}
}
answer(cr);
// cout << cr << '\n';
}
}
// int G[MAXN], R[MAXN][2];
// signed main(){
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
// int n, m, p, q;
// cin >> n >> m >> p >> q;
// for (int i=0;i<m;i++){
// cin >> R[i][0] >> R[i][1];
// }
// for (int i=0;i<q;i++) cin >> G[i];
// count_routes(n, m, p, R, q, G);
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
12880 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
12880 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
12880 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
