| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 967896 |
2024-04-23T04:49:36 Z |
8pete8 |
Regions (IOI09_regions) |
C++17 |
|
866 ms |
109300 KB |
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib>
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
//#define int long long
//#define double long double
const int mod=1e9+7,mxn=2e5+5,lg=60,inf=1e9,minf=-1e9,mx=3e4;
int root=700,st;
vector<int>adj[mxn+10];
int re[mxn+10],recnt[mxn+10],sz[mxn+10],hvyp[mxn+10],up[mxn+10];
int tin[mxn+10],tout[mxn+10],T=0;
void getsz(int cur){sz[cur]=1;for(auto i:adj[cur])getsz(i),sz[cur]+=sz[i];}
void dfs(int cur,int hvypa){
tin[cur]=++T;
int hvy=0;
hvyp[cur]=hvypa;
for(auto i:adj[cur]){
if(sz[i]>sz[hvy])hvy=i;
up[i]=cur;
}
for(auto i:adj[cur])if(i!=hvy)dfs(i,i);
if(hvy)dfs(hvy,hvypa);
tout[cur]=T;
}
bool cmp(int a,int b){return tin[a]<tin[b];}
struct chain{
vector<int>have,com;
vector<vector<int>>pos;
void init(){
if(have.empty())return;
for(auto i:have)com.pb(re[i]);
sort(all(com));
sort(all(have),cmp);
com.erase(unique(all(com)),com.end());
pos.resize(com.size());
for(auto i:have)pos[lb(all(com),re[i])-com.begin()].pb(tin[i]);
return;
}
int get(int x,int id){
auto it=lb(all(com),id)-com.begin();
if(it>=pos.size()||com[it]!=id)return 0;
if(pos[it].empty())return 0;
if(pos[it].back()<=x)return pos[it].size();
else return upper_bound(all(pos[it]),x)-pos[it].begin();
}
}t[mxn+10];//parent of hvy chain
vector<int>pos[mxn+10];
vector<int>have[mxn+10];
int pre[mx][500];
int32_t main(){
fastio
int n,r,q;cin>>n>>r>>q;
root=sqrt(n);
for(int i=1;i<=n;i++){
if(i!=1){
int b;cin>>b;
adj[b].pb(i);
}
cin>>re[i];
recnt[re[i]]++;
have[re[i]].pb(i);
}
getsz(1);
dfs(1,1);
for(int i=1;i<=n;i++)t[hvyp[i]].have.pb(i);
for(int i=1;i<=n;i++)t[i].init(),pos[re[i]].pb(tin[i]);
vector<int>k;
for(int i=1;i<=r;i++){
if(recnt[i]<root)continue;
k.pb(i);
}
for(int i=1;i<=n;i++){
int cur=i;
while(hvyp[cur]!=1){
for(int j=0;j<k.size();j++){
pre[re[i]][j]+=t[hvyp[cur]].get(tin[cur],k[j]);
}
cur=up[hvyp[cur]];
}
for(int j=0;j<k.size();j++)pre[re[i]][j]+=t[hvyp[cur]].get(tin[cur],k[j]);
}
//qry r1,r2 cout<<pre[r2][pos r1];
while(q--){
int a,b;cin>>a>>b;
if(recnt[a]<root){
int ans=0;
for(auto j:have[a]){
int l=lb(all(pos[b]),tin[j])-pos[b].begin();
if(l==pos[b].size())continue;
int r=lb(all(pos[b]),tout[j])-pos[b].begin();
if(r==pos[b].size())r--;
ans+=(r-l+1);
}
cout<<ans<<'\n';
}
else{
auto it=lb(all(k),a)-k.begin();
cout<<pre[b][it]<<'\n';
}
}
}
/*
sqrt decomp
if region cnt<=sqrtn -> burte force sqrtn{
do euler tour keep vector of pos in euler tour for each region
when qry r1,r2 loop through all sqrtn node then qry in subtree of that node
qry-> bs l,r in vector of r2; ans+=(r-l+1)
}
else we precompute the region to other region (keep sqrtn(r)){
use merge sort tree +hld? (too costly?){
dont need merge sort?
keep chain then each chain keep vector of pos for each region
}
}
*/
Compilation message
regions.cpp: In member function 'int chain::get(int, int)':
regions.cpp:72:8: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if(it>=pos.size()||com[it]!=id)return 0;
| ~~^~~~~~~~~~~~
regions.cpp: In function 'int32_t main()':
regions.cpp:106:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int j=0;j<k.size();j++){
| ~^~~~~~~~~
regions.cpp:111:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int j=0;j<k.size();j++)pre[re[i]][j]+=t[hvyp[cur]].get(tin[cur],k[j]);
| ~^~~~~~~~~
regions.cpp:120:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | if(l==pos[b].size())continue;
| ~^~~~~~~~~~~~~~~
regions.cpp:122:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | if(r==pos[b].size())r--;
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
13 ms |
35160 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
7 ms |
35160 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
7 ms |
35160 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
6 ms |
35412 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
6 ms |
35148 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
6 ms |
35160 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
7 ms |
35160 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
7 ms |
35416 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
8 ms |
35672 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
10 ms |
36184 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
11 ms |
36696 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
13 ms |
36964 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
16 ms |
38124 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
26 ms |
40592 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
21 ms |
42324 KB |
Time limit exceeded (wall clock) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
109 ms |
43776 KB |
Time limit exceeded (wall clock) |
| 2 |
Execution timed out |
95 ms |
46544 KB |
Time limit exceeded (wall clock) |
| 3 |
Execution timed out |
72 ms |
45056 KB |
Time limit exceeded (wall clock) |
| 4 |
Execution timed out |
20 ms |
38744 KB |
Time limit exceeded (wall clock) |
| 5 |
Execution timed out |
22 ms |
39184 KB |
Time limit exceeded (wall clock) |
| 6 |
Execution timed out |
233 ms |
55316 KB |
Time limit exceeded (wall clock) |
| 7 |
Execution timed out |
252 ms |
63764 KB |
Time limit exceeded (wall clock) |
| 8 |
Execution timed out |
427 ms |
66964 KB |
Time limit exceeded (wall clock) |
| 9 |
Execution timed out |
102 ms |
51396 KB |
Time limit exceeded (wall clock) |
| 10 |
Execution timed out |
866 ms |
102696 KB |
Time limit exceeded (wall clock) |
| 11 |
Execution timed out |
135 ms |
60024 KB |
Time limit exceeded (wall clock) |
| 12 |
Execution timed out |
160 ms |
87344 KB |
Time limit exceeded (wall clock) |
| 13 |
Execution timed out |
134 ms |
87572 KB |
Time limit exceeded (wall clock) |
| 14 |
Execution timed out |
466 ms |
95796 KB |
Time limit exceeded (wall clock) |
| 15 |
Execution timed out |
137 ms |
104652 KB |
Time limit exceeded (wall clock) |
| 16 |
Execution timed out |
134 ms |
109300 KB |
Time limit exceeded (wall clock) |
| 17 |
Execution timed out |
274 ms |
98592 KB |
Time limit exceeded (wall clock) |
