/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#define maxn 200005
#define maxr 20005
#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];
int ans[maxr][maxr];
int sz[maxn] , id[maxn];
int pre[maxn];
int timer;
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];
}
}
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])
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)
for(auto& e : c[i])
if(used[e] == false)
dfs2(e , par[e] , 0 , color[e]);
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() , id[e] + sz[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:101:13: warning: unused variable 'x' [-Wunused-variable]
101 | int x;
| ^
regions.cpp:109:9: warning: unused variable 'sq' [-Wunused-variable]
109 | int sq = 500;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
24152 KB |
Output is correct |
2 |
Correct |
5 ms |
24152 KB |
Output is correct |
3 |
Correct |
4 ms |
24152 KB |
Output is correct |
4 |
Correct |
6 ms |
24152 KB |
Output is correct |
5 |
Correct |
8 ms |
24152 KB |
Output is correct |
6 |
Correct |
14 ms |
24152 KB |
Output is correct |
7 |
Correct |
18 ms |
24404 KB |
Output is correct |
8 |
Correct |
23 ms |
24408 KB |
Output is correct |
9 |
Correct |
23 ms |
24664 KB |
Output is correct |
10 |
Correct |
55 ms |
24664 KB |
Output is correct |
11 |
Correct |
87 ms |
24920 KB |
Output is correct |
12 |
Correct |
108 ms |
25432 KB |
Output is correct |
13 |
Correct |
126 ms |
25432 KB |
Output is correct |
14 |
Correct |
200 ms |
25756 KB |
Output is correct |
15 |
Correct |
186 ms |
28760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
72 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Runtime error |
78 ms |
131072 KB |
Execution killed with signal 9 |
3 |
Runtime error |
77 ms |
131072 KB |
Execution killed with signal 9 |
4 |
Correct |
189 ms |
25924 KB |
Output is correct |
5 |
Correct |
259 ms |
27648 KB |
Output is correct |
6 |
Correct |
1074 ms |
26980 KB |
Output is correct |
7 |
Correct |
1355 ms |
27992 KB |
Output is correct |
8 |
Correct |
1004 ms |
33112 KB |
Output is correct |
9 |
Correct |
1734 ms |
32848 KB |
Output is correct |
10 |
Runtime error |
26 ms |
28504 KB |
Execution killed with signal 11 |
11 |
Runtime error |
26 ms |
28504 KB |
Execution killed with signal 11 |
12 |
Runtime error |
98 ms |
131072 KB |
Execution killed with signal 9 |
13 |
Runtime error |
99 ms |
131072 KB |
Execution killed with signal 9 |
14 |
Runtime error |
112 ms |
131072 KB |
Execution killed with signal 9 |
15 |
Runtime error |
26 ms |
28504 KB |
Execution killed with signal 11 |
16 |
Runtime error |
27 ms |
28504 KB |
Execution killed with signal 11 |
17 |
Runtime error |
95 ms |
131072 KB |
Execution killed with signal 9 |