oj.uz

Submission #933459

# Submission time Handle Problem Language Result Execution time Memory
933459 2024-02-25T17:21:32 Z thunopro Regions (IOI09_regions) C++14
100 / 100
 3255 ms 45204 KB 
#include<bits/stdc++.h>
using namespace std ; 
#define maxn 200009
#define ll long long 
#define pb push_back 
#define fi first 
#define se second 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
const int mod = 1e9+7 ;
const int INF = 1e9 ; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 

template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } 

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a >= mod ) a -= mod ; 
	if ( a < 0 ) a += mod ; 
}

void rf () 
{
	freopen ("bai1.inp","r",stdin) ;
}

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
	else return 1ll*res*res%mod ; 
}

int n , region , nq ; 

vi adjList [maxn] , R [maxn] , FR [maxn] ;  
int group [maxn] ; 
int num , ver [maxn] , cnt [maxn] ; 
int tin [maxn] , tout [maxn] , timeDfs ; 
int ans [202][maxn] ; 
int euler [maxn] ; 
void dfs ( int u ) 
{
	tin [u] = ++ timeDfs ; 
	euler [timeDfs] = u ; 
	for ( auto v : adjList [u] ) dfs (v) ; 
	tout [u] = timeDfs ; 
}
int main () 
{
	ios_base::sync_with_stdio(0); 
	cin.tie(0);cout.tie(0); 
//	rf () ; 
	cin >> n >> region >> nq ; 
	for ( int i = 1 ; i <= n ; i ++ ) 
	{
		int x , r ; 
		if ( i != 1 ) cin >> x , adjList [x] . pb (i) ; 
		cin >> r ;
		group [i] = r ; 
		R [r] . pb (i) ; 
	}
	
	dfs (1) ; 

	for ( int i = 1 ; i <= n ; i ++ ) FR[group[i]] . pb (tin[i]) ; 
	for ( int i = 1 ; i <= region ; i ++ ) sort (FR[i].begin(),FR[i].end()) ; 
	
	for ( int r = 1 ; r <= region ; r ++ ) 
	{
		if ( R [r].size () >= 1000 ) 
		{
			++ num ; 
			ver [r] = num ; 
			for ( auto x : R [r] ) 
			{
				cnt [tin[x]] ++ , cnt [tout[x]+1] -- ; 
			}
			for ( int i = 1 ; i <= n ; i ++ ) 
			{
				cnt [i] += cnt [i-1] ; 
				ans [num][group[euler[i]]] += cnt [i] ; 
			}
			for ( int i = 1 ; i <= n ; i ++ ) cnt [i] = 0 ; 
		}
	}
	
	for ( int r = 1 ; r <= nq ; r ++ ) 
	{
		int x , y ; cin >> x >> y ; 
		if ( ver [x] != 0 ) cout << ans [ver[x]][y] << endl ; 
		else 
		{
			int res = 0 ; 
			for ( auto i : R [x] ) 
			{
				res += upper_bound (FR[y].begin(),FR[y].end(),tout[i]) - lower_bound (FR[y].begin(),FR[y].end(),tin[i]) ; 
			}
			cout << res << endl ; 
		}
	}
}

Compilation message

regions.cpp: In function 'void rf()':
regions.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 5 ms 17096 KB Output is correct
3 Correct 5 ms 16984 KB Output is correct
4 Correct 5 ms 16984 KB Output is correct
5 Correct 7 ms 16984 KB Output is correct
6 Correct 14 ms 16984 KB Output is correct
7 Correct 14 ms 17240 KB Output is correct
8 Correct 23 ms 17492 KB Output is correct
9 Correct 25 ms 17496 KB Output is correct
10 Correct 41 ms 17496 KB Output is correct
11 Correct 74 ms 17736 KB Output is correct
12 Correct 84 ms 18264 KB Output is correct
13 Correct 123 ms 18080 KB Output is correct
14 Correct 181 ms 18776 KB Output is correct
15 Correct 210 ms 20768 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1464 ms 25524 KB Output is correct
2 Correct 1662 ms 28672 KB Output is correct
3 Correct 2228 ms 33000 KB Output is correct
4 Correct 160 ms 18776 KB Output is correct
5 Correct 237 ms 20148 KB Output is correct
6 Correct 1063 ms 21752 KB Output is correct
7 Correct 1282 ms 22940 KB Output is correct
8 Correct 934 ms 26752 KB Output is correct
9 Correct 1760 ms 27904 KB Output is correct
10 Correct 3255 ms 31800 KB Output is correct
11 Correct 3187 ms 28096 KB Output is correct
12 Correct 911 ms 31092 KB Output is correct
13 Correct 1276 ms 31000 KB Output is correct
14 Correct 1523 ms 39200 KB Output is correct
15 Correct 2234 ms 34420 KB Output is correct
16 Correct 2084 ms 37724 KB Output is correct
17 Correct 1969 ms 45204 KB Output is correct