이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
#define INF 1145141919
#define rep(i, n) for (int i=0; i<(n); i++)
#define _1 first
#define _2 second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef pair<int, int> P;
int N, M, T, Q;
vector<P> G[150000];
vector<int> G2[150000*2];
int best[150000];
int F[30][150000*2];
int A[2000];
int D[150000*2];
int C[2][150000*2];
inline int fg(P p) {
int x = p._2, e = p._1;
if (best[x] == e) return x+N;
else return x;
}
inline int go(int x, int s) {
for (int k=29; k>=0; k--) if ((s>>k)&1) x = F[k][x];
return x;
}
int bfs(int s) {
queue<int> q;
rep(i, 2*N) D[i] = INF;
D[s] = 0;
q.push(s);
int ret = INF;
while (!q.empty()) {
int x = q.front(); q.pop();
for (int t : G2[x]) {
if (t == s) ret = min(ret, D[x]+1);
if (D[t] > D[x]+1) {
D[t] = D[x]+1;
q.push(t);
}
}
}
return ret;
}
void count_routes(int n, int m, int p, int edges[][2], int q, int g[]) {
N = n, M = m, T = p, Q = q;
rep(i, N) G[i].clear();
rep(i, M) {
G[edges[i][0]].pb(P(i, edges[i][1]));
G[edges[i][1]].pb(P(i, edges[i][0]));
}
rep(i, N) best[i] = G[i][0]._1;
rep(i, N) {
F[0][i] = fg(G[i][0]);
F[0][i+N] = fg((G[i].size()>=2)? G[i][1] : G[i][0]);
}
rep(i, 2*N) G2[i].clear();
rep(i, 2*N) G2[F[0][i]].pb(i);
rep(k, 29) rep(i, 2*N) F[k+1][i] = F[k][F[k][i]];
vector<int> S[2];
int r[2];
r[0] = bfs(T ); rep(i, N) S[0].pb(D[i]); sort(all(S[0]), greater<int>());
r[1] = bfs(T+N); rep(i, N) S[1].pb(D[i]); sort(all(S[1]), greater<int>());
rep(i, 2) rep(t, 2*N) C[i][t] = 0;
vector<P> qs;
rep(i, Q) qs.pb(P(g[i], i));
sort(all(qs));
rep(_, Q) {
int k = qs[_]._1, q = qs[_]._2;
int ctr = 0;
rep(i, 2) {
while (!S[i].empty() && S[i].back() <= k) {
int t = S[i].back();
if (r[i] != INF) C[i][t%r[i]]++;
else if (t == k) ctr++;
S[i].pop_back();
}
}
rep(i, 2) if (r[i] != INF) ctr += C[i][k%r[i]];
A[q] = ctr;
}
rep(i, Q) answer(A[i]);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |