oj.uz

Submission #369365

# Submission time Handle Problem Language Result Execution time Memory
369365 2021-02-21T12:27:59 Z AmineWeslati Regions (IOI09_regions) C++14
50 / 100
 8000 ms 50616 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=400;
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 22 ms 28652 KB Output is correct
2 Correct 24 ms 28524 KB Output is correct
3 Correct 26 ms 28524 KB Output is correct
4 Correct 25 ms 28524 KB Output is correct
5 Correct 31 ms 28524 KB Output is correct
6 Correct 36 ms 28652 KB Output is correct
7 Correct 58 ms 28652 KB Output is correct
8 Correct 62 ms 28696 KB Output is correct
9 Correct 78 ms 29036 KB Output is correct
10 Correct 141 ms 28908 KB Output is correct
11 Correct 200 ms 29164 KB Output is correct
12 Correct 189 ms 29804 KB Output is correct
13 Correct 224 ms 29292 KB Output is correct
14 Correct 340 ms 29804 KB Output is correct
15 Correct 299 ms 32276 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8070 ms 32284 KB Time limit exceeded
2 Correct 3845 ms 31316 KB Output is correct
3 Execution timed out 8042 ms 34168 KB Time limit exceeded
4 Correct 396 ms 29936 KB Output is correct
5 Correct 546 ms 31340 KB Output is correct
6 Correct 5770 ms 45932 KB Output is correct
7 Correct 3484 ms 43628 KB Output is correct
8 Execution timed out 8028 ms 43636 KB Time limit exceeded
9 Correct 3376 ms 36332 KB Output is correct
10 Execution timed out 8038 ms 50616 KB Time limit exceeded
11 Correct 4400 ms 35564 KB Output is correct
12 Execution timed out 8035 ms 36928 KB Time limit exceeded
13 Execution timed out 8037 ms 36844 KB Time limit exceeded
14 Execution timed out 8098 ms 38004 KB Time limit exceeded
15 Execution timed out 8096 ms 41708 KB Time limit exceeded
16 Execution timed out 8090 ms 49132 KB Time limit exceeded
17 Execution timed out 8096 ms 48236 KB Time limit exceeded