oj.uz

Submission #369361

# Submission time Handle Problem Language Result Execution time Memory
369361 2021-02-21T12:24:31 Z AmineWeslati Regions (IOI09_regions) C++14
45 / 100
 8000 ms 37356 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 = 1e5 + 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 12 ms 14592 KB Output is correct
2 Correct 11 ms 14444 KB Output is correct
3 Correct 13 ms 14444 KB Output is correct
4 Correct 15 ms 14444 KB Output is correct
5 Correct 25 ms 14444 KB Output is correct
6 Correct 27 ms 14572 KB Output is correct
7 Correct 35 ms 14444 KB Output is correct
8 Correct 43 ms 14572 KB Output is correct
9 Correct 65 ms 14956 KB Output is correct
10 Correct 89 ms 14956 KB Output is correct
11 Correct 141 ms 15084 KB Output is correct
12 Correct 182 ms 15724 KB Output is correct
13 Correct 192 ms 15356 KB Output is correct
14 Correct 278 ms 15768 KB Output is correct
15 Correct 328 ms 18180 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8051 ms 18580 KB Time limit exceeded
2 Correct 3819 ms 17184 KB Output is correct
3 Execution timed out 8058 ms 20076 KB Time limit exceeded
4 Correct 203 ms 15844 KB Output is correct
5 Correct 381 ms 17356 KB Output is correct
6 Correct 1655 ms 16876 KB Output is correct
7 Correct 1858 ms 17652 KB Output is correct
8 Correct 1345 ms 22252 KB Output is correct
9 Runtime error 64 ms 36460 KB Execution killed with signal 11
10 Runtime error 63 ms 37220 KB Execution killed with signal 11
11 Runtime error 63 ms 34668 KB Execution killed with signal 11
12 Runtime error 82 ms 36964 KB Execution killed with signal 11
13 Runtime error 66 ms 36332 KB Execution killed with signal 11
14 Runtime error 78 ms 36040 KB Execution killed with signal 11
15 Runtime error 65 ms 37356 KB Execution killed with signal 11
16 Runtime error 63 ms 37344 KB Execution killed with signal 11
17 Runtime error 64 ms 37092 KB Execution killed with signal 11