oj.uz

Submission #933455

# Submission time Handle Problem Language Result Execution time Memory
933455 2024-02-25T17:19:49 Z thunopro Regions (IOI09_regions) C++14
55 / 100
 3209 ms 44164 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] ; 

void dfs ( int u ) 
{
	tin [u] = ++ timeDfs ; 
	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[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 18416 KB Output is correct
2 Correct 4 ms 18260 KB Output is correct
3 Correct 6 ms 18264 KB Output is correct
4 Correct 7 ms 18360 KB Output is correct
5 Correct 8 ms 18264 KB Output is correct
6 Correct 14 ms 18364 KB Output is correct
7 Correct 17 ms 18264 KB Output is correct
8 Correct 19 ms 18772 KB Output is correct
9 Correct 28 ms 18776 KB Output is correct
10 Correct 46 ms 18776 KB Output is correct
11 Correct 75 ms 18872 KB Output is correct
12 Correct 84 ms 19284 KB Output is correct
13 Correct 120 ms 19204 KB Output is correct
14 Correct 201 ms 19492 KB Output is correct
15 Correct 191 ms 21136 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1568 ms 25996 KB Output isn't correct
2 Incorrect 1664 ms 27124 KB Output isn't correct
3 Incorrect 2020 ms 31204 KB Output isn't correct
4 Correct 176 ms 19596 KB Output is correct
5 Correct 217 ms 20624 KB Output is correct
6 Correct 1038 ms 20428 KB Output is correct
7 Correct 1251 ms 21372 KB Output is correct
8 Correct 894 ms 25012 KB Output is correct
9 Correct 1755 ms 25768 KB Output is correct
10 Correct 3161 ms 29128 KB Output is correct
11 Correct 3209 ms 25412 KB Output is correct
12 Incorrect 835 ms 28888 KB Output isn't correct
13 Incorrect 1223 ms 28800 KB Output isn't correct
14 Incorrect 1467 ms 36936 KB Output isn't correct
15 Incorrect 2239 ms 31832 KB Output isn't correct
16 Incorrect 1946 ms 34388 KB Output isn't correct
17 Incorrect 1976 ms 44164 KB Output isn't correct