/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#define maxn 200005
#define maxr 25005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;
using namespace std;
typedef long long ll;
typedef pair <ll , ll> pll;
typedef pair <int , int> pii;
typedef long double ld;
typedef unsigned long long ull;
map <int , int> br[maxn];
int n , r , q;
vector <int> v[maxn];
int color[maxn];
vector <int> c[maxr];
map <int , int> ans[maxr];
int sz[maxn] , id[maxn];
int pre[maxn];
int timer;
int tout[maxn];
vector <int> tt[maxn];
void dfs(int node , int par)
{
id[node] = timer;
pre[timer] = color[node];
sz[node] = 1;
tt[color[node]].pb(timer);
timer++;
for(auto& nb : v[node])
{
if(nb == par)
continue;
dfs(nb , node);
sz[node] += sz[nb];
}
tout[node] = timer;
}
bool used[maxn];
void dfs2(int node , int par , int br , int col)
{
if(color[node] == col)
used[node] = true;
ans[col][color[node]] += br;
for(auto& nb : v[node])
{
if(nb == par)
continue;
dfs2(nb , node , br + (col == color[node]) , col);
}
}
int par[maxn];
void read()
{
cin >> n >> r >> q;
for(int i = 1; i <= n; i++)
{
if(i == 1)
{
cin >> color[i];
c[color[i]].pb(i);
continue;
}
int x;
cin >> par[i] >> color[i];
c[color[i]].pb(i);
v[par[i]].pb(i);
v[i].pb(par[i]);
}
int sq = 500;
timer = 0;
dfs(1 , 0);
for(int i = 1; i <= r; i++)
if(c[i].size() > 500)
dfs2(c[i][0] , par[c[i][0]] , 0 , color[c[i][0]]);
int x , y;
while(q--)
{
cin >> x >> y;
if(c[x].size() > 500)
{
cout << ans[x][y] << endl;
cout.flush();
continue;
}
int curr = 0;
for(auto& e : c[x])
curr += (upper_bound(tt[y].begin() , tt[y].end() , tout[e] - 1) - tt[y].begin())
- (lower_bound(tt[y].begin() , tt[y].end() , id[e]) - tt[y].begin());
cout << curr << endl;
cout.flush();
}
}
int main()
{
/**#ifdef ONLINE_JUDGE
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif*/
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
///startT = std::chrono::high_resolution_clock::now();
read();
return 0;
}
Compilation message
regions.cpp: In function 'void read()':
regions.cpp:109:13: warning: unused variable 'x' [-Wunused-variable]
109 | int x;
| ^
regions.cpp:117:9: warning: unused variable 'sq' [-Wunused-variable]
117 | int sq = 500;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
25688 KB |
Output is correct |
2 |
Correct |
4 ms |
25688 KB |
Output is correct |
3 |
Correct |
5 ms |
25688 KB |
Output is correct |
4 |
Correct |
5 ms |
25688 KB |
Output is correct |
5 |
Correct |
7 ms |
25636 KB |
Output is correct |
6 |
Correct |
12 ms |
25688 KB |
Output is correct |
7 |
Correct |
20 ms |
25688 KB |
Output is correct |
8 |
Correct |
15 ms |
25688 KB |
Output is correct |
9 |
Correct |
39 ms |
26196 KB |
Output is correct |
10 |
Correct |
51 ms |
26196 KB |
Output is correct |
11 |
Correct |
90 ms |
26456 KB |
Output is correct |
12 |
Correct |
100 ms |
26968 KB |
Output is correct |
13 |
Correct |
124 ms |
26712 KB |
Output is correct |
14 |
Correct |
207 ms |
27224 KB |
Output is correct |
15 |
Correct |
174 ms |
30040 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1483 ms |
30296 KB |
Output isn't correct |
2 |
Incorrect |
1694 ms |
30092 KB |
Output isn't correct |
3 |
Incorrect |
2167 ms |
32848 KB |
Output isn't correct |
4 |
Correct |
172 ms |
27224 KB |
Output is correct |
5 |
Correct |
261 ms |
29016 KB |
Output is correct |
6 |
Correct |
1073 ms |
28504 KB |
Output is correct |
7 |
Correct |
1265 ms |
29528 KB |
Output is correct |
8 |
Correct |
965 ms |
34648 KB |
Output is correct |
9 |
Correct |
1761 ms |
34124 KB |
Output is correct |
10 |
Correct |
3197 ms |
39504 KB |
Output is correct |
11 |
Correct |
3216 ms |
35852 KB |
Output is correct |
12 |
Incorrect |
1070 ms |
36112 KB |
Output isn't correct |
13 |
Incorrect |
1512 ms |
37352 KB |
Output isn't correct |
14 |
Incorrect |
1648 ms |
39356 KB |
Output isn't correct |
15 |
Incorrect |
2447 ms |
44592 KB |
Output isn't correct |
16 |
Incorrect |
2372 ms |
55164 KB |
Output isn't correct |
17 |
Incorrect |
2309 ms |
61576 KB |
Output isn't correct |