Submission #967901

# Submission time Handle Problem Language Result Execution time Memory
967901 2024-04-23T04:54:36 Z 8pete8 Regions (IOI09_regions) C++17
3 / 100
2653 ms 108828 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<<endl;
		}
		else{
			auto it=lb(all(k),a)-k.begin();
			cout<<pre[b][it]<<endl;
		}
	}
}
/*
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 Incorrect 8 ms 35160 KB Output isn't correct
2 Incorrect 8 ms 35160 KB Output isn't correct
3 Incorrect 8 ms 33112 KB Output isn't correct
4 Incorrect 9 ms 33068 KB Output isn't correct
5 Incorrect 11 ms 35160 KB Output isn't correct
6 Correct 15 ms 33084 KB Output is correct
7 Incorrect 20 ms 35160 KB Output isn't correct
8 Incorrect 25 ms 33368 KB Output isn't correct
9 Correct 39 ms 33624 KB Output is correct
10 Incorrect 50 ms 34136 KB Output isn't correct
11 Incorrect 76 ms 36732 KB Output isn't correct
12 Incorrect 105 ms 36892 KB Output isn't correct
13 Incorrect 127 ms 37976 KB Output isn't correct
14 Incorrect 190 ms 38744 KB Output isn't correct
15 Correct 222 ms 38932 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 1128 ms 40536 KB Output isn't correct
2 Incorrect 1200 ms 46184 KB Output isn't correct
3 Incorrect 1827 ms 45220 KB Output isn't correct
4 Incorrect 184 ms 38744 KB Output isn't correct
5 Incorrect 242 ms 39412 KB Output isn't correct
6 Incorrect 543 ms 55472 KB Output isn't correct
7 Incorrect 960 ms 63748 KB Output isn't correct
8 Incorrect 1073 ms 66088 KB Output isn't correct
9 Incorrect 1587 ms 51296 KB Output isn't correct
10 Incorrect 2653 ms 102556 KB Output isn't correct
11 Incorrect 2335 ms 60088 KB Output isn't correct
12 Incorrect 954 ms 85016 KB Output isn't correct
13 Incorrect 1359 ms 85652 KB Output isn't correct
14 Incorrect 1749 ms 95556 KB Output isn't correct
15 Incorrect 2179 ms 104304 KB Output isn't correct
16 Incorrect 2191 ms 108828 KB Output isn't correct
17 Incorrect 2168 ms 98100 KB Output isn't correct