oj.uz

Submission #431982

# Submission time Handle Problem Language Result Execution time Memory
431982 2021-06-17T18:02:33 Z amunduzbaev Regions (IOI09_regions) C++14
1 / 100
 543 ms 93540 KB 
/* made by amunduzbaev */
 
#include "bits/stdc++.h"
 
using namespace std;
 
//~ #include <ext/pb_ds/assoc_container.hpp>
//~ #include <ext/pb_ds/tree_policy.hpp>
//~ using namespace __gnu_pbds;
//~ template<class T> using oset = tree<T, 
//~ null_type, less_equal<T>, rb_tree_tag, 
//~ tree_order_statistics_node_update>;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define mem(arr, v) memset(arr, v, sizeof arr)
//~ #define int long long
#define degub(x) cout<<#x<<" : "<<x<<"\n"
#define GG cout<<"here"<<endl;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T> bool umax(T& a, const T& b) { return a < b ? a = b, true : false; }
template<int sz> using tut = array<int, sz>;
void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
	freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
 
const int N = 2e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
const int B = 500;
 
#define MULTI 0
int n, m, k, t, q, ans, res, a[N];
int last[N], id[N], cnt[N];
int bs[N / B + 10][N];
int sb[N][N / B + 10];
int tin[N], tout[N];
vii edges[N];
vpii cmp[N];

//~ BIG_SMALL BIG_BIG
int cur;
void bsdfs(int u, int cur, int p = -1, int cnt = 0){
	if(id[a[u]] == cur) cnt++;
	//~ cout<<cur<<" "<<id[a[u]]<<" "<<cnt<<"\n";
	bs[cur][a[u]] += cnt;
	for(auto x : edges[u]) bsdfs(x, cur, u, cnt);
}

//~ SMALL_BIG
map<int, int> sbdfs(int u, int p = -1){
	map<int, int> cnt;
	tin[u] = t++;
	for(auto x : edges[u]) {
		map<int, int> tmp = sbdfs(x, u);
		if(sz(tmp) > sz(cnt)) swap(cnt, tmp);
		for(auto x : tmp) cnt[x.ff] += x.ss;
	}  tout[u] = t - 1;
	if(id[a[u]]) cnt[id[a[u]]]++;
	else for(auto x : cnt) sb[a[u]][x.ff] += x.ss;
	return cnt;
}

bool par(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }

map<pii, int> cach;

void solve(int t_case){
	cin>>n>>m>>q;
	cin>>a[1];
	for(int i=2;i<=n;i++){
		int p; cin>>p>>a[i];
		edges[p].pb(i);
	}
	
	for(int i=1;i<=n;i++) cnt[a[i]]++;
	int last = 1;
	for(int i=1;i<=m;i++){
		if(cnt[i] > B) id[i] = last++;
	}
	
	for(int i=1;i<last;i++) bsdfs(1, i);
	sbdfs(1);
	for(int i=1;i<=n;i++) cmp[a[i]].pb({tin[i], tout[i]});
	for(int i=1;i<=m;i++) sort(all(cmp[i]));

	for(int i=1;i<=q;i++){
		int x, b; cin>>x>>b;
		int rr;
		if(cach.count({x, b})) { cout<<cach[{x, b}]<<"\n"; continue; }
		if(id[x]) { rr = bs[id[x]][b]; cout<<bs[id[x]][b]<<"\n"; }
		else if(id[b]) { rr = sb[x][id[b]]; cout<<sb[x][id[b]]<<"\n"; }
		else { 
			int res = 0; 
			//~ SMALL_SMALL
			for(auto tt : cmp[x]){
				int lx = lb(all(cmp[b]), mp(tt.ff, -1)) - cmp[b].begin();
				int rx = ub(all(cmp[b]), mp(tt.ss, tt.ss)) - cmp[b].begin();
				res += rx - lx;
			} cout<<res<<"\n"; rr = res;
		} cout.flush();
		cach[{x, b}] = rr;
	}
}

signed main(){
	NeedForSpeed
	if(MULTI){
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} else solve(1);
	return 0;
}

Compilation message

regions.cpp: In function 'void usaco(std::string)':
regions.cpp:38:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 | void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:39:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9672 KB Output is correct
2 Execution timed out 6 ms 9672 KB Time limit exceeded (wall clock)
3 Execution timed out 6 ms 9672 KB Time limit exceeded (wall clock)
4 Execution timed out 6 ms 9672 KB Time limit exceeded (wall clock)
5 Execution timed out 6 ms 9672 KB Time limit exceeded (wall clock)
6 Execution timed out 7 ms 9916 KB Time limit exceeded (wall clock)
7 Execution timed out 7 ms 9824 KB Time limit exceeded (wall clock)
8 Execution timed out 10 ms 9856 KB Time limit exceeded (wall clock)
9 Execution timed out 14 ms 10880 KB Time limit exceeded (wall clock)
10 Execution timed out 12 ms 10272 KB Time limit exceeded (wall clock)
11 Execution timed out 13 ms 10568 KB Time limit exceeded (wall clock)
12 Execution timed out 17 ms 11592 KB Time limit exceeded (wall clock)
13 Execution timed out 22 ms 10696 KB Time limit exceeded (wall clock)
14 Execution timed out 23 ms 11336 KB Time limit exceeded (wall clock)
15 Execution timed out 33 ms 18888 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 58 ms 16592 KB Time limit exceeded (wall clock)
2 Execution timed out 96 ms 13892 KB Time limit exceeded (wall clock)
3 Execution timed out 58 ms 21056 KB Time limit exceeded (wall clock)
4 Execution timed out 116 ms 12096 KB Time limit exceeded (wall clock)
5 Execution timed out 48 ms 16188 KB Time limit exceeded (wall clock)
6 Execution timed out 27 ms 13224 KB Time limit exceeded (wall clock)
7 Execution timed out 34 ms 14044 KB Time limit exceeded (wall clock)
8 Execution timed out 66 ms 26944 KB Time limit exceeded (wall clock)
9 Execution timed out 122 ms 21304 KB Time limit exceeded (wall clock)
10 Execution timed out 141 ms 34724 KB Time limit exceeded (wall clock)
11 Execution timed out 132 ms 18884 KB Time limit exceeded (wall clock)
12 Execution timed out 186 ms 46196 KB Time limit exceeded (wall clock)
13 Execution timed out 232 ms 48448 KB Time limit exceeded (wall clock)
14 Execution timed out 543 ms 54208 KB Time limit exceeded (wall clock)
15 Execution timed out 169 ms 73048 KB Time limit exceeded (wall clock)
16 Execution timed out 149 ms 93540 KB Time limit exceeded (wall clock)
17 Execution timed out 233 ms 82932 KB Time limit exceeded (wall clock)