답안 #967905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
967905 2024-04-23T04:57:07 Z 8pete8 Regions (IOI09_regions) C++17
4 / 100
2576 ms 109428 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=ub(all(pos[b]),tout[j])-pos[b].begin()-1;
				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;
      |        ~^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 35132 KB Output is correct
2 Incorrect 10 ms 35160 KB Output isn't correct
3 Incorrect 11 ms 35160 KB Output isn't correct
4 Incorrect 10 ms 35160 KB Output isn't correct
5 Incorrect 11 ms 35160 KB Output isn't correct
6 Correct 16 ms 35160 KB Output is correct
7 Incorrect 23 ms 35160 KB Output isn't correct
8 Incorrect 26 ms 35416 KB Output isn't correct
9 Correct 34 ms 35672 KB Output is correct
10 Incorrect 59 ms 36156 KB Output isn't correct
11 Incorrect 84 ms 36656 KB Output isn't correct
12 Incorrect 96 ms 36952 KB Output isn't correct
13 Incorrect 123 ms 37920 KB Output isn't correct
14 Incorrect 186 ms 40512 KB Output isn't correct
15 Correct 236 ms 42336 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1160 ms 43772 KB Output isn't correct
2 Incorrect 1248 ms 46124 KB Output isn't correct
3 Incorrect 1805 ms 45224 KB Output isn't correct
4 Incorrect 185 ms 38744 KB Output isn't correct
5 Incorrect 213 ms 39392 KB Output isn't correct
6 Incorrect 572 ms 55380 KB Output isn't correct
7 Incorrect 892 ms 63816 KB Output isn't correct
8 Incorrect 1012 ms 67192 KB Output isn't correct
9 Incorrect 1518 ms 51432 KB Output isn't correct
10 Incorrect 2576 ms 103352 KB Output isn't correct
11 Incorrect 2335 ms 60016 KB Output isn't correct
12 Incorrect 1008 ms 87356 KB Output isn't correct
13 Incorrect 1338 ms 87776 KB Output isn't correct
14 Incorrect 1833 ms 95956 KB Output isn't correct
15 Incorrect 2219 ms 104796 KB Output isn't correct
16 Incorrect 2131 ms 109428 KB Output isn't correct
17 Incorrect 2272 ms 98116 KB Output isn't correct