oj.uz

Submission #249429

# Submission time Handle Problem Language Result Execution time Memory
249429 2020-07-15T03:01:56 Z MohamedAhmed04 Regions (IOI09_regions) C++14
50 / 100
 3158 ms 131072 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[MAX] , 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[now][arr[node]] += cnt ;
	ans2[arr[node]][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)) ;
	for(int i = 1 ; i <= r ; ++i)
	{
		sort(RegNodes[i].begin() , RegNodes[i].end()) ;
		if(Reg[i] >= SZ)
			now = i , dfs2(1 , 0) ;
	}
	stack<int>s ;
	while(q--)
	{
		int a , b ;
		cin>>a>>b ;
		if(Reg[a] >= SZ)
			cout<<ans1[a][b]<<endl ;
		else if(Reg[b] >= SZ)
			cout<<ans2[a][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 8 ms 9728 KB Output is correct
4 Correct 9 ms 9728 KB Output is correct
5 Correct 12 ms 9856 KB Output is correct
6 Correct 17 ms 9856 KB Output is correct
7 Correct 28 ms 9856 KB Output is correct
8 Correct 27 ms 9856 KB Output is correct
9 Correct 45 ms 10368 KB Output is correct
10 Correct 63 ms 10368 KB Output is correct
11 Correct 133 ms 10624 KB Output is correct
12 Correct 118 ms 11256 KB Output is correct
13 Correct 146 ms 10880 KB Output is correct
14 Correct 149 ms 11912 KB Output is correct
15 Correct 204 ms 14580 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 15252 KB Output is correct
2 Correct 1151 ms 14324 KB Output is correct
3 Correct 1877 ms 17140 KB Output is correct
4 Correct 358 ms 11640 KB Output is correct
5 Correct 391 ms 13300 KB Output is correct
6 Runtime error 61 ms 50424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 100 ms 64112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 105 ms 74352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 1855 ms 19640 KB Output is correct
10 Runtime error 164 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Correct 3158 ms 19380 KB Output is correct
12 Runtime error 117 ms 42240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 117 ms 42604 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 218 ms 113344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 116 ms 50672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 127 ms 61204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 180 ms 130924 KB Execution killed with signal 11 (could be triggered by violating memory limits)