oj.uz

Submission #933450

# Submission time Handle Problem Language Result Execution time Memory
933450 2024-02-25T17:13:51 Z thunopro Regions (IOI09_regions) C++14
25 / 100
 2162 ms 131072 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 [102][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 () >= 250 ) 
		{
			++ 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 18008 KB Output is correct
2 Correct 4 ms 18008 KB Output is correct
3 Correct 5 ms 18008 KB Output is correct
4 Correct 6 ms 18008 KB Output is correct
5 Correct 8 ms 18008 KB Output is correct
6 Correct 14 ms 18008 KB Output is correct
7 Correct 18 ms 18008 KB Output is correct
8 Correct 18 ms 18008 KB Output is correct
9 Correct 34 ms 18264 KB Output is correct
10 Correct 55 ms 18520 KB Output is correct
11 Correct 79 ms 18776 KB Output is correct
12 Correct 94 ms 19080 KB Output is correct
13 Correct 110 ms 18776 KB Output is correct
14 Correct 190 ms 19288 KB Output is correct
15 Correct 187 ms 20948 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1274 ms 40296 KB Output isn't correct
2 Incorrect 1062 ms 88628 KB Output isn't correct
3 Incorrect 2055 ms 31316 KB Output isn't correct
4 Correct 160 ms 19292 KB Output is correct
5 Correct 212 ms 20704 KB Output is correct
6 Incorrect 341 ms 67580 KB Output isn't correct
7 Incorrect 780 ms 62344 KB Output isn't correct
8 Incorrect 696 ms 102680 KB Output isn't correct
9 Incorrect 1330 ms 103836 KB Output isn't correct
10 Incorrect 1885 ms 106908 KB Output isn't correct
11 Runtime error 205 ms 131072 KB Execution killed with signal 9
12 Incorrect 954 ms 28876 KB Output isn't correct
13 Incorrect 1269 ms 28844 KB Output isn't correct
14 Incorrect 1511 ms 45132 KB Output isn't correct
15 Incorrect 2162 ms 31824 KB Output isn't correct
16 Incorrect 1986 ms 61116 KB Output isn't correct
17 Incorrect 2041 ms 50316 KB Output isn't correct