| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 861986 |
2023-10-17T10:27:42 Z |
vjudge1 |
Regions (IOI09_regions) |
C++14 |
|
2655 ms |
29392 KB |
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define endl printf("\n")
#define flush fflush(stdout)
#define pp pop_back
#define pr printf
#define sc scanf
#define debug(x) pr("%s , %i\n" , #x , x)
#define bg begin
#define arr(x) array<int , (x)>
typedef long long ll;
typedef pair<int , int> pii;
typedef long double ld;
const ll MOD = int(1e9) + 7;
const int root = 450;
const int inroot = 200000 / root + 1;
ll Sum(ll a , ll b){
ll res = a + b;
if(res > MOD) return (res - MOD);
if(res < 0) return (res + MOD);
return res;
}
ll Mul(ll a , ll b){
return (a * b) % MOD;
}
ll Pow(ll a , ll b){
ll res = 1;
while(b){
if((b & 1)) res = Mul(res , a);
a = Mul(a , a);
b >>= 1;
}
return res;
}
int n , r , q;
int wrg[200000];
vector<int> rgs[25000];
vector<int> g[200000];
int times[200000][2];
vector<int> tour[25000];
int mem[inroot][25000];
int rginx[200000];
int ps[200000];
int timer = -1;
void dfs0(int v = 0){
times[v][0] = ++timer;
tour[wrg[v]].pb(timer);
for(int u : g[v]) dfs0(u);
times[v][1] = timer;
}
void bfs0(int e){
fill(&ps[0] , &ps[n] , 0);
queue<arr(2)> q;
q.push({0 , -1});
while(!q.empty()){
auto d = q.front();
q.pop();
if(d[0] != 0){
ps[d[0]] = ps[d[1]];
if(wrg[d[1]] == e) ps[d[0]]++;
}
mem[rginx[e]][wrg[d[0]]] += ps[d[0]];
for(int u : g[d[0]]){
q.push({u , d[0]});
}
}
}
void init(){
int counter = 0;
for(int i = 0 ; i < r ; i++){
if(!rgs[i].empty() and (int)rgs[i].size() > root){
rginx[i] = counter;
bfs0(i);
counter++;
}
}
}
int f(int a , int c){
int res = 0;
for(int el : rgs[a]){
if(times[el][0] == times[el][1]) continue;
auto itr1 = ub(tour[c].bg() , tour[c].end() , times[el][0]);
auto itr2 = ub(tour[c].bg() , tour[c].end() , times[el][1]);
if(tour[c].empty() or itr2 == tour[c].bg()) continue;
itr2--;
res += int(itr2 - itr1 + 1);
}
return res;
}
int main(){
sc("%i%i%i" , &n , &r , &q);
int d;
sc("%i" , &d);
rgs[d - 1].pb(0);
wrg[0] = d - 1;
for(int i = 1 ; i < n ; i++){
int p;
sc("%i%i" , &p , &d);
rgs[d - 1].pb(i);
g[p - 1].pb(i);
wrg[i] = d - 1;
}
dfs0();
init();
for(int i = 0 ; i < q ; i++){
int a , b;
sc("%i%i" , &a , &b);
a-- , b--;
if(rgs[a].empty()) pr("0\n");
else if((int)rgs[a].size() <= root) pr("%i\n" , f(a , b));
else pr("%i\n" , mem[rginx[a]][b]);
flush;
}
/*
ZZZZZZZ A M M IIIIIII N N
Z A A M M M M I NN N
Z A A M M M M I N N N
Z AAAAAAA M M M I N N N
Z A A M M I N N N
Z A A M M I N NN
ZZZZZZZ A A M M IIIIIII N N TREE
*/
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:101:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | sc("%i%i%i" , &n , &r , &q);
| ^
regions.cpp:103:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | sc("%i" , &d);
| ^
regions.cpp:108:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | sc("%i%i" , &p , &d);
| ^
regions.cpp:118:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
118 | sc("%i%i" , &a , &b);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9560 KB |
Output is correct |
| 2 |
Correct |
3 ms |
9560 KB |
Output is correct |
| 3 |
Correct |
3 ms |
9560 KB |
Output is correct |
| 4 |
Correct |
4 ms |
9560 KB |
Output is correct |
| 5 |
Correct |
6 ms |
9560 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9560 KB |
Output is correct |
| 7 |
Correct |
13 ms |
9560 KB |
Output is correct |
| 8 |
Correct |
21 ms |
9816 KB |
Output is correct |
| 9 |
Correct |
25 ms |
10072 KB |
Output is correct |
| 10 |
Correct |
44 ms |
10324 KB |
Output is correct |
| 11 |
Correct |
74 ms |
10216 KB |
Output is correct |
| 12 |
Correct |
91 ms |
10584 KB |
Output is correct |
| 13 |
Correct |
108 ms |
10396 KB |
Output is correct |
| 14 |
Correct |
197 ms |
10840 KB |
Output is correct |
| 15 |
Correct |
205 ms |
12696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1338 ms |
17772 KB |
Output is correct |
| 2 |
Correct |
1190 ms |
16776 KB |
Output is correct |
| 3 |
Correct |
2181 ms |
19116 KB |
Output is correct |
| 4 |
Correct |
159 ms |
11092 KB |
Output is correct |
| 5 |
Correct |
218 ms |
12252 KB |
Output is correct |
| 6 |
Correct |
340 ms |
20468 KB |
Output is correct |
| 7 |
Correct |
1113 ms |
17232 KB |
Output is correct |
| 8 |
Correct |
724 ms |
29120 KB |
Output is correct |
| 9 |
Correct |
1675 ms |
17884 KB |
Output is correct |
| 10 |
Correct |
2655 ms |
29392 KB |
Output is correct |
| 11 |
Correct |
2598 ms |
17252 KB |
Output is correct |
| 12 |
Correct |
908 ms |
21048 KB |
Output is correct |
| 13 |
Correct |
1312 ms |
20900 KB |
Output is correct |
| 14 |
Correct |
1456 ms |
23008 KB |
Output is correct |
| 15 |
Correct |
2191 ms |
24272 KB |
Output is correct |
| 16 |
Correct |
2060 ms |
27584 KB |
Output is correct |
| 17 |
Correct |
2032 ms |
28492 KB |
Output is correct |
