| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 355542 | parsabahrami | Regions (IOI09_regions) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 2e5 + 10, SQ = 450;
map<int, int> Cup[N], Cdown[N], C1[N], C2[N]; vector<pii> vec[N];
int A[N], S[N], St[N], Ft[N], n, R, q, tim; vector<int> adj[N];
void preDFS(int v) {
St[v] = tim++;
for (int u : adj[v]) {
preDFS(u);
}
Ft[v] = tim;
}
void DFS(int v, int p = -1) {
if (~p) {
Cup[v] = Cup[p];
if (S[A[p]] > SQ) Cup[v][A[p]]++;
}
for (int u : adj[v]) {
DFS(u, v);
unordered_map<int, int> tmp = Cdown[u];
if (SZ(tmp) > SZ(Cdown[v])) Cdown[v].swap(tmp);
for (pii x : tmp) Cdown[v][x.F] += x.S;
if (S[A[u]] > SQ) Cdown[v][A[u]]++;
}
}
int main() {
scanf("%d%d%d%d", &n, &R, &q, &A[1]);
for (int i = 2; i <= n; i++) {
int p; scanf("%d%d", &p, &A[i]);
adj[p].push_back(i);
}
preDFS(1);
for (int i = 1; i <= n; i++) vec[A[i]].push_back({St[i], i});
for (int i = 1; i <= R; i++) sort(vec[i].begin(), vec[i].end()), S[i] = SZ(vec[i]);
DFS(1);
for (int i = 1; i <= n; i++) {
for (pii x : Cup[i]) C1[A[i]][x.F] += x.S;
for (pii x : Cdown[i]) C2[A[i]][x.F] += x.S;
}
for (; q; q--) {
int r1, r2; scanf("%d%d", &r1, &r2);
if (S[r1] > SQ) printf("%d\n", C1[r2][r1]);
else if (S[r2] > SQ) printf("%d\n", C2[r1][r2]);
else {
int l = 0, r = 0, ret = 0;
for (pii x : vec[r1]) {
int v = x.S;
while (r < S[r2] && vec[r2][r].F < Ft[v]) r++;
while (l < r && vec[r2][l].F < St[v]) l++;
if (l == S[r2] || !r) continue;
int u = vec[r2][l].S, w = vec[r2][r - 1].S;
if (St[v] <= St[u] && Ft[u] <= Ft[v] && St[v] <= St[w] && Ft[w] <= Ft[v]) ret += r - l;
}
printf("%d\n", ret);
}
fflush(stdout);
}
return 0;
}