oj.uz

Submission #369362

# Submission time Handle Problem Language Result Execution time Memory
369362 2021-02-21T12:26:27 Z AmineWeslati Regions (IOI09_regions) C++14
45 / 100
 8000 ms 37384 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 13 ms 14444 KB Output is correct
2 Correct 11 ms 14444 KB Output is correct
3 Correct 13 ms 14444 KB Output is correct
4 Correct 16 ms 14444 KB Output is correct
5 Correct 19 ms 14444 KB Output is correct
6 Correct 37 ms 14572 KB Output is correct
7 Correct 56 ms 14444 KB Output is correct
8 Correct 39 ms 14572 KB Output is correct
9 Correct 54 ms 14976 KB Output is correct
10 Correct 89 ms 14828 KB Output is correct
11 Correct 135 ms 15084 KB Output is correct
12 Correct 129 ms 15596 KB Output is correct
13 Correct 147 ms 15240 KB Output is correct
14 Correct 315 ms 15768 KB Output is correct
15 Correct 360 ms 18180 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8060 ms 18444 KB Time limit exceeded
2 Correct 3721 ms 17196 KB Output is correct
3 Execution timed out 8048 ms 20092 KB Time limit exceeded
4 Correct 317 ms 15852 KB Output is correct
5 Correct 453 ms 17356 KB Output is correct
6 Correct 1374 ms 16876 KB Output is correct
7 Correct 2058 ms 17772 KB Output is correct
8 Correct 1608 ms 22288 KB Output is correct
9 Runtime error 64 ms 36460 KB Execution killed with signal 11
10 Runtime error 63 ms 37348 KB Execution killed with signal 11
11 Runtime error 62 ms 34668 KB Execution killed with signal 11
12 Runtime error 64 ms 36836 KB Execution killed with signal 11
13 Runtime error 63 ms 36332 KB Execution killed with signal 11
14 Runtime error 63 ms 36076 KB Execution killed with signal 11
15 Runtime error 64 ms 37356 KB Execution killed with signal 11
16 Runtime error 65 ms 37384 KB Execution killed with signal 11
17 Runtime error 76 ms 37348 KB Execution killed with signal 11