#include<bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 150005;
struct Edge {
int u, v;
} edge[MAXN];
vector<ii> adj[MAXN];
vector<int> adjp[2 * MAXN], comp[2 * MAXN], B[2 * MAXN];
int h[2 * MAXN], timeIn[2 * MAXN], timeOut[2 * MAXN], result[2 * MAXN];
int firstToLoop[2 * MAXN], firstInLoop[2 * MAXN], loopOf[2 * MAXN], posInComp[2 * MAXN];
int deg[2 * MAXN], pa[2 * MAXN], idc[2 * MAXN], idn[2 * MAXN], numNode, numEdge, numQuery, lastNode;
bool dx[2 * MAXN], ok[2 * MAXN];
inline int getLeftNode(int id) {
return (id >= numEdge) ? edge[id - numEdge].v : edge[id].u;
}
int timeIn0;
void preDfs(int u, int p) {
timeIn[u] = ++timeIn0;
if(ok[u])
B[h[u]].push_back(timeIn[u]);
for (int it = 0; it < int(adjp[u].size()); ++it) {
int v(adjp[u][it]);
if(v != p) {
h[v] = 1 + h[u];
preDfs(v, u);
}
}
timeOut[u] = timeIn0;
}
void count_routes(int _N, int _M, int _P, int _R[][2], int _Q, int _G[]) {
numNode = _N, numEdge = _M, lastNode = _P, numQuery = _Q;
for (int i = 0; i < _M; ++i) {
int u(_R[i][0]), v(_R[i][1]);
edge[i] = {u, v};
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
for (int u = 0; u < numNode; ++u) {
int id0 = adj[u][0].se;
int id1 = (adj[u].size() > 1 ? adj[u][1].se : 1e9+7);
bool type0 = (u == edge[adj[u][0].se].v);
bool type1 = (adj[u].size() > 1 && (u == edge[adj[u][1].se].v));
for (int it = 0; it < int(adj[u].size()); ++it) {
int v(adj[u][it].fi), id(adj[u][it].se);
bool type = !(u == edge[id].v);
if(it == 0) {
idn[u] = id + !type * numEdge;
ok[idn[u]] = 1;
}
pa[id + type * numEdge] = (id != id0 || id1 >= 1e9+7) ? id0 + type0 * numEdge : id1 + type1 * numEdge;
++deg[pa[id + type * numEdge]];
}
}
int numComp(0);
for (int id = 0; id < 2 * numEdge; ++id) {
if(deg[id] || dx[id])
continue;
vector<int> tmpn;
int tmp(id);
while(!dx[tmp]) {
dx[tmp] = 1;
tmpn.push_back(tmp);
tmp = pa[tmp];
}
int szn(tmpn.size());
for (int it = 0; it <= szn; ++it) {
if(it == szn || tmpn[it] == tmp) {
if(it < szn) {
for (int jt = it; jt < szn; ++jt) {
posInComp[tmpn[jt]] = jt - it;
comp[numComp].push_back(tmpn[jt]);
firstInLoop[tmpn[jt]] = tmpn[jt];
loopOf[tmpn[jt]] = szn - it;
firstToLoop[tmpn[jt]] = 0;
idc[tmpn[jt]] = numComp;
}
++numComp;
}
if(it > 0) {
adjp[tmp].push_back(tmpn[it - 1]);
for (int jt = 0; jt < it; ++jt) {
posInComp[tmpn[jt]] = jt;
comp[numComp].push_back(tmpn[jt]);
firstToLoop[tmpn[jt]] = it - jt + firstToLoop[tmp];
firstInLoop[tmpn[jt]] = firstInLoop[tmp];
idc[tmpn[jt]] = numComp;
if(jt + 1 < it)
adjp[tmpn[jt + 1]].push_back(tmpn[jt]);
}
++numComp;
}
break;
}
}
}
for (int id = 0; id < 2 * numEdge; ++id) {
if(!deg[id] || dx[id])
continue;
int tmp(id);
while(!dx[tmp]) {
dx[tmp] = 1;
posInComp[tmp] = comp[numComp].size();
comp[numComp].push_back(tmp);
idc[tmp] = numComp;
firstToLoop[tmp] = 0;
firstInLoop[tmp] = tmp;
tmp = pa[tmp];
}
int szn(comp[numComp].size());
for (int it = 0; it < szn; ++it)
loopOf[comp[numComp][it]] = szn;
++numComp;
}
for (int id = 0; id < 2 * numEdge; ++id) {
if(!timeIn[id])
preDfs(id, -1);
/*cout << id << ": ";
for (int it = 0; it < int(adjp[id].size()); ++it)
cout << adjp[id][it] << ' ';
cout << '\n';*/
}
for (int t = 0; t < numQuery; ++t) {
int K(_G[t]), cnt(0);
if(K <= 2 * numEdge) {
for (int id = 0; id < 2 * numEdge; ++id) {
if(adjp[id].size() > 0 && getLeftNode(id) == lastNode && h[id] + K <= 2 * numEdge) {
int ub = upper_bound(B[h[id] + K].begin(), B[h[id] + K].end(), timeOut[id]) - B[h[id] + K].begin();
int lb = lower_bound(B[h[id] + K].begin(), B[h[id] + K].end(), timeIn[id]) - B[h[id] + K].begin();
cnt += max(0, ub - lb);
/*cout << id << ' ' << lb << ' ' << ub << ' ' << timeIn[id] << ' ' << timeOut[id] << ' ';
if(lb < ub)
cout << B[h[id] + K][lb] << ' ';
cout << '\n';*/
}
}
}
for (int u = 0; u < numNode; ++u) {
if(firstToLoop[idn[u]] > K)
continue;
int id(firstInLoop[idn[u]]), posn = (posInComp[id] + K - firstToLoop[idn[u]]) % loopOf[id];
cnt += (getLeftNode(comp[idc[id]][posn]) == lastNode);
}
answer(cnt);
}
}
Compilation message
garden.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
8 | #pragma GCC optimization ("O3")
|
garden.cpp:9: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
9 | #pragma GCC optimization ("unroll-loops")
|
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:76:17: warning: unused variable 'v' [-Wunused-variable]
76 | int v(adj[u][it].fi), id(adj[u][it].se);
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
25300 KB |
Output is correct |
2 |
Correct |
12 ms |
25188 KB |
Output is correct |
3 |
Correct |
13 ms |
25300 KB |
Output is correct |
4 |
Correct |
12 ms |
25044 KB |
Output is correct |
5 |
Correct |
12 ms |
24984 KB |
Output is correct |
6 |
Correct |
14 ms |
25600 KB |
Output is correct |
7 |
Correct |
12 ms |
25056 KB |
Output is correct |
8 |
Correct |
13 ms |
25208 KB |
Output is correct |
9 |
Correct |
17 ms |
26572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
25300 KB |
Output is correct |
2 |
Correct |
12 ms |
25188 KB |
Output is correct |
3 |
Correct |
13 ms |
25300 KB |
Output is correct |
4 |
Correct |
12 ms |
25044 KB |
Output is correct |
5 |
Correct |
12 ms |
24984 KB |
Output is correct |
6 |
Correct |
14 ms |
25600 KB |
Output is correct |
7 |
Correct |
12 ms |
25056 KB |
Output is correct |
8 |
Correct |
13 ms |
25208 KB |
Output is correct |
9 |
Correct |
17 ms |
26572 KB |
Output is correct |
10 |
Correct |
14 ms |
25044 KB |
Output is correct |
11 |
Correct |
25 ms |
29012 KB |
Output is correct |
12 |
Correct |
58 ms |
35236 KB |
Output is correct |
13 |
Correct |
43 ms |
37132 KB |
Output is correct |
14 |
Correct |
216 ms |
54272 KB |
Output is correct |
15 |
Correct |
227 ms |
55192 KB |
Output is correct |
16 |
Correct |
196 ms |
51536 KB |
Output is correct |
17 |
Correct |
160 ms |
50900 KB |
Output is correct |
18 |
Correct |
73 ms |
35932 KB |
Output is correct |
19 |
Correct |
209 ms |
54280 KB |
Output is correct |
20 |
Correct |
241 ms |
55252 KB |
Output is correct |
21 |
Correct |
243 ms |
52364 KB |
Output is correct |
22 |
Correct |
183 ms |
50956 KB |
Output is correct |
23 |
Correct |
209 ms |
55508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
25300 KB |
Output is correct |
2 |
Correct |
12 ms |
25188 KB |
Output is correct |
3 |
Correct |
13 ms |
25300 KB |
Output is correct |
4 |
Correct |
12 ms |
25044 KB |
Output is correct |
5 |
Correct |
12 ms |
24984 KB |
Output is correct |
6 |
Correct |
14 ms |
25600 KB |
Output is correct |
7 |
Correct |
12 ms |
25056 KB |
Output is correct |
8 |
Correct |
13 ms |
25208 KB |
Output is correct |
9 |
Correct |
17 ms |
26572 KB |
Output is correct |
10 |
Correct |
14 ms |
25044 KB |
Output is correct |
11 |
Correct |
25 ms |
29012 KB |
Output is correct |
12 |
Correct |
58 ms |
35236 KB |
Output is correct |
13 |
Correct |
43 ms |
37132 KB |
Output is correct |
14 |
Correct |
216 ms |
54272 KB |
Output is correct |
15 |
Correct |
227 ms |
55192 KB |
Output is correct |
16 |
Correct |
196 ms |
51536 KB |
Output is correct |
17 |
Correct |
160 ms |
50900 KB |
Output is correct |
18 |
Correct |
73 ms |
35932 KB |
Output is correct |
19 |
Correct |
209 ms |
54280 KB |
Output is correct |
20 |
Correct |
241 ms |
55252 KB |
Output is correct |
21 |
Correct |
243 ms |
52364 KB |
Output is correct |
22 |
Correct |
183 ms |
50956 KB |
Output is correct |
23 |
Correct |
209 ms |
55508 KB |
Output is correct |
24 |
Incorrect |
14 ms |
25044 KB |
Output isn't correct |
25 |
Halted |
0 ms |
0 KB |
- |