//
// ~oisín~ C++ Template
//
#include <bits/stdc++.h>
#define MX_N 200005
#define mp make_pair
#define mod7 1000000007
#define modpi 314159
#define PI 3.141592653589793238
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a) a.begin(),a.end()
#define fi first
#define se second
#define ll long long int
#define ull unsigned long long int
int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] = {+0, +0, +1, -1};
int dy4[4] = {+1, -1, +0, +0};
ll gcd(ull a, ull b){
return (a==0)?b:gcd(b%a,a);
}
ll lcm(ull a, ull b){
return a*(b/gcd(a,b));
}
const long long INF = 1e18;
using namespace std;
int N, R, Q;
int H[MX_N];
int p[MX_N];
vector<int> adj[MX_N];
vector<int> r[MX_N];
vector<pair<int, bool> > ord;
void dfs(int at){
ord.pb({at, 0});
r[H[at]].pb((int)ord.size()-1);
for(int to : adj[at]){
if(p[at] == to){
continue;
}
dfs(to);
}
ord.pb({at, 1});
r[H[at]].pb((int)ord.size()-1);
}
//map<pair<int, int>, int> cache;
int cache[5000][5000];
int main(){
cin >> N >> R >> Q;
int c = 1000000;
cin >> H[0];
--H[0];
for(int i=1;i<N;++i){
cin >> p[i] >> H[i];
--p[i], --H[i];
adj[p[i]].pb(i);
}
dfs(0);
for(int j=0;j<R;++j){
if((int)r[j].size() >= c){
for(int i=0;i<R;++i){
if(i == j){
continue;
}
vector<int> tmp;
for(auto P : r[i]){
tmp.pb(P);
}
for(auto P : r[j]){
tmp.pb(P);
}
sort(All(tmp));
int cntA = 0, cntB = 0;
int ans = 0;
for(auto ii : tmp){
auto P = ord[ii];
if(H[P.fi] == i){
if(P.se == 0){
++cntA;
}else{
--cntA;
}
}else{
if(P.se == 0){
++cntB;
ans += cntA;
}else{
--cntB;
}
}
}
//cache[make_pair(i, j)] = ans;
cache[i][j] = ans;
}
}
}
for(int i=0;i<R;++i){
if((int)r[i].size() >= c){
for(int j=0;j<R;++j){
if(i == j){
continue;
}
vector<int> tmp;
for(auto P : r[i]){
tmp.pb(P);
}
for(auto P : r[j]){
tmp.pb(P);
}
sort(All(tmp));
int cntA = 0, cntB = 0;
int ans = 0;
for(auto ii : tmp){
auto P = ord[ii];
if(H[P.fi] == i){
if(P.se == 0){
++cntA;
}else{
--cntA;
}
}else{
if(P.se == 0){
++cntB;
ans += cntA;
}else{
--cntB;
}
}
}
cache[i][j] = ans;
//cache[make_pair(i, j)] = ans;
}
}
}
while(Q--){
int r1, r2;
cin >> r1 >> r2;
--r1, --r2;
if((int)r[r1].size() >= c){
cout << cache[r1][r2] << endl;
cout.flush();
}else{
vector<int> tmp;
for(auto P : r[r1]){
tmp.pb(P);
}
for(auto P : r[r2]){
tmp.pb(P);
}
sort(All(tmp));
int cntA = 0, cntB = 0;
int ans = 0;
for(auto ii : tmp){
auto P = ord[ii];
if(H[P.fi] == r1){
if(P.se == 0){
++cntA;
}else{
--cntA;
}
}else{
if(P.se == 0){
++cntB;
ans += cntA;
}else{
--cntB;
}
}
}
cout << ans << endl;
cout.flush();
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
9672 KB |
Output is correct |
2 |
Correct |
6 ms |
9672 KB |
Output is correct |
3 |
Correct |
8 ms |
9672 KB |
Output is correct |
4 |
Correct |
8 ms |
9672 KB |
Output is correct |
5 |
Correct |
14 ms |
9672 KB |
Output is correct |
6 |
Correct |
34 ms |
9800 KB |
Output is correct |
7 |
Correct |
37 ms |
9800 KB |
Output is correct |
8 |
Correct |
46 ms |
9800 KB |
Output is correct |
9 |
Correct |
81 ms |
10440 KB |
Output is correct |
10 |
Correct |
98 ms |
10440 KB |
Output is correct |
11 |
Correct |
148 ms |
10668 KB |
Output is correct |
12 |
Correct |
258 ms |
11588 KB |
Output is correct |
13 |
Correct |
267 ms |
11036 KB |
Output is correct |
14 |
Correct |
599 ms |
11704 KB |
Output is correct |
15 |
Correct |
809 ms |
15900 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
8068 ms |
16564 KB |
Time limit exceeded |
2 |
Execution timed out |
8080 ms |
14764 KB |
Time limit exceeded |
3 |
Execution timed out |
8005 ms |
18892 KB |
Time limit exceeded |
4 |
Correct |
410 ms |
11708 KB |
Output is correct |
5 |
Correct |
679 ms |
14520 KB |
Output is correct |
6 |
Correct |
3228 ms |
13296 KB |
Output is correct |
7 |
Correct |
3864 ms |
15344 KB |
Output is correct |
8 |
Correct |
3739 ms |
22000 KB |
Output is correct |
9 |
Correct |
5527 ms |
22704 KB |
Output is correct |
10 |
Execution timed out |
8054 ms |
29608 KB |
Time limit exceeded |
11 |
Execution timed out |
8032 ms |
21020 KB |
Time limit exceeded |
12 |
Execution timed out |
8061 ms |
23328 KB |
Time limit exceeded |
13 |
Execution timed out |
8089 ms |
23944 KB |
Time limit exceeded |
14 |
Execution timed out |
8084 ms |
23400 KB |
Time limit exceeded |
15 |
Execution timed out |
8079 ms |
28968 KB |
Time limit exceeded |
16 |
Execution timed out |
8037 ms |
38596 KB |
Time limit exceeded |
17 |
Execution timed out |
8085 ms |
36524 KB |
Time limit exceeded |