oj.uz

Submission #369364

# Submission time Handle Problem Language Result Execution time Memory
369364 2021-02-21T12:27:36 Z AmineWeslati Regions (IOI09_regions) C++14
60 / 100
 8000 ms 49132 KB 
//Never stop trying
#include "bits/stdc++.h"
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 2e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}
#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
/////////////////////////ONLY CLEAN CODES ALLOWED/////////////////////////

const int C=800;
int N,R,Q; 
vi a(MX),adj[MX],cnt(MX,0),vec[MX],vec2[MX],in(MX),out(MX);
unordered_map<int,int>mp[MX];

//mp[x][y]
void dfs(int u, int c){
	for(auto v: adj[u]){
		mp[c][a[v]]++;
		dfs(v,c);
	}
}
void precompute1(){
	FOR(i,1,R+1) if(cnt[i]>C){
		FOR(j,1,N+1) if(a[j]==i) dfs(j,i);
	}
}

//in[u],out[u]
//vec2[c]

int cntr=0;
void euler(int u=1, int p=1){
	in[u]=++cntr;
	for(auto v: adj[u]) euler(v,u);
	out[u]=cntr;
}
void precompute2(){
	euler();
	FOR(i,1,N+1) vec2[a[i]].pb(in[i]);
	FOR(i,1,R+1) sort(all(vec2[i]));
}


int solve(int l, int r, int c){
	if(l>r) return 0;
	return upper_bound(all(vec2[c]),r)-lower_bound(all(vec2[c]),l);
}

int main() {
    boost; IO();

    cin>>N>>R>>Q;
    FOR(i,1,N+1){
    	if(i>1){
    		int j; cin>>j;
    		adj[j].pb(i);
    	}
    	cin>>a[i];
    	vec[a[i]].pb(i);
    	cnt[a[i]]++;
    }

    precompute1();
    precompute2();

    while(Q--){
    	int x,y; cin>>x>>y;
    	if(cnt[x]>C){
    		cout << mp[x][y] << endl;
    		cout.flush();
    	}
    	else{
    		int ans=0;
    		for(auto u: vec[x]){
    			int l=in[u],r=out[u];
    			ans+=solve(l+1,r,y);
    		}
    		cout << ans << endl;
    		cout.flush();
    	}
    }

    return 0;
}
//Change your approach

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28524 KB Output is correct
2 Correct 20 ms 28524 KB Output is correct
3 Correct 22 ms 28524 KB Output is correct
4 Correct 24 ms 28524 KB Output is correct
5 Correct 29 ms 28524 KB Output is correct
6 Correct 37 ms 28652 KB Output is correct
7 Correct 54 ms 28652 KB Output is correct
8 Correct 55 ms 28780 KB Output is correct
9 Correct 71 ms 29164 KB Output is correct
10 Correct 97 ms 29036 KB Output is correct
11 Correct 156 ms 29292 KB Output is correct
12 Correct 194 ms 29676 KB Output is correct
13 Correct 185 ms 29292 KB Output is correct
14 Correct 330 ms 29932 KB Output is correct
15 Correct 317 ms 32364 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8019 ms 32536 KB Time limit exceeded
2 Correct 3841 ms 31360 KB Output is correct
3 Execution timed out 8041 ms 34156 KB Time limit exceeded
4 Correct 349 ms 29932 KB Output is correct
5 Correct 414 ms 31452 KB Output is correct
6 Correct 1716 ms 30900 KB Output is correct
7 Correct 2296 ms 31744 KB Output is correct
8 Correct 1902 ms 36332 KB Output is correct
9 Correct 2920 ms 36300 KB Output is correct
10 Correct 5718 ms 40996 KB Output is correct
11 Correct 4750 ms 35644 KB Output is correct
12 Execution timed out 8080 ms 36852 KB Time limit exceeded
13 Execution timed out 8050 ms 36848 KB Time limit exceeded
14 Execution timed out 8071 ms 37960 KB Time limit exceeded
15 Execution timed out 8069 ms 41708 KB Time limit exceeded
16 Execution timed out 8093 ms 49132 KB Time limit exceeded
17 Execution timed out 8031 ms 48200 KB Time limit exceeded