oj.uz

Submission #249430

# Submission time Handle Problem Language Result Execution time Memory
249430 2020-07-15T03:05:32 Z MohamedAhmed04 Regions (IOI09_regions) C++14
100 / 100
 2816 ms 78080 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e5 + 10 ;
const int MAXSZ = 450 ;
const int MAXR = 25005 ;

int arr[MAX] , in[MAX] , out[MAX] ;
int Reg[MAXR] , id[MAXR] , ans1[MAXSZ][MAXR] , ans2[MAXR][MAXSZ] ;
vector<int>nodes ;
int n , r , q ;

vector< vector<int> >adj(MAX) ;
vector< vector< pair<int , int> > >RegNodes(MAX) ;

int tim = 0 ;

void dfs(int node)
{
	nodes.push_back(node) ;
	in[node] = ++tim ;
	for(auto &child : adj[node])
		dfs(child) ;
	out[node] = tim ;
}

int now ;

int dfs2(int node , int cnt)
{
	int x = 0 ;
	for(auto &child : adj[node])
		x += dfs2(child , cnt + (arr[node] == now)) ;
	ans1[id[now]][arr[node]] += cnt ;
	ans2[arr[node]][id[now]] += x ;
	return (x + (arr[node] == now)) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>r>>q ;
	cin>>arr[1] ;
	for(int i = 2 ; i <= n ; ++i)
	{
		int x ;
		cin>>x>>arr[i] ;
		adj[x].push_back(i) ;
	}
	dfs(1) ;
	for(int i = 1 ; i <= n ; ++i)
	{
		Reg[arr[i]]++ ;
		RegNodes[arr[i]].emplace_back(in[i] , i) ;
	}
	int SZ = ceil(sqrt(n)) ;
	int cur = 0 ;
	for(int i = 1 ; i <= r ; ++i)
	{
		sort(RegNodes[i].begin() , RegNodes[i].end()) ;
		if(Reg[i] >= SZ)
			++cur , id[i] = cur , now = i , dfs2(1 , 0) ;
	}
	stack<int>s ;
	while(q--)
	{
		int a , b ;
		cin>>a>>b ;
		if(Reg[a] >= SZ)
			cout<<ans1[id[a]][b]<<endl ;
		else if(Reg[b] >= SZ)
			cout<<ans2[a][id[b]]<<endl ;
		else
		{
			while(s.size() > 0)
				s.pop() ;
			int idx1 = 0 , idx2 = 0 , cnt = 0 ;
			for(int i = 0 ; i < Reg[a] + Reg[b] ; ++i)
			{
				int x = 1e9 , y = 1e9 ;
				if(idx1 != Reg[a])
					x = RegNodes[a][idx1].first ;
				if(idx2 != Reg[b])
					y = RegNodes[b][idx2].first ;
				while(s.size() > 0 && s.top() < min(x , y))
					s.pop() ;
				if(x < y)
					s.push(out[RegNodes[a][idx1].second]) , idx1++ ;
				else
					cnt += s.size() , idx2++ ;
			}
			cout<<cnt<<endl ;
		}
	}
	return 0 ;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 7 ms 9728 KB Output is correct
4 Correct 11 ms 9728 KB Output is correct
5 Correct 12 ms 9856 KB Output is correct
6 Correct 21 ms 9856 KB Output is correct
7 Correct 31 ms 9856 KB Output is correct
8 Correct 36 ms 9856 KB Output is correct
9 Correct 48 ms 10368 KB Output is correct
10 Correct 72 ms 10368 KB Output is correct
11 Correct 123 ms 10744 KB Output is correct
12 Correct 157 ms 11136 KB Output is correct
13 Correct 193 ms 10940 KB Output is correct
14 Correct 247 ms 11904 KB Output is correct
15 Correct 257 ms 14560 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1067 ms 15228 KB Output is correct
2 Correct 1339 ms 14068 KB Output is correct
3 Correct 1937 ms 17140 KB Output is correct
4 Correct 290 ms 11640 KB Output is correct
5 Correct 360 ms 13180 KB Output is correct
6 Correct 725 ms 26872 KB Output is correct
7 Correct 1048 ms 33648 KB Output is correct
8 Correct 1217 ms 40816 KB Output is correct
9 Correct 2253 ms 19628 KB Output is correct
10 Correct 2173 ms 78080 KB Output is correct
11 Correct 2816 ms 19380 KB Output is correct
12 Correct 1055 ms 49020 KB Output is correct
13 Correct 1433 ms 49228 KB Output is correct
14 Correct 2131 ms 57712 KB Output is correct
15 Correct 2324 ms 69420 KB Output is correct
16 Correct 2468 ms 74664 KB Output is correct
17 Correct 2378 ms 66188 KB Output is correct