oj.uz

Submission #411262

# Submission time Handle Problem Language Result Execution time Memory
411262 2021-05-24T21:01:49 Z AugustinasJucas Regions (IOI09_regions) C++14
70 / 100
 8000 ms 78712 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
const int dydis = 2e5 + 10;
int n, r, q;
vector<int> dideli; // regionai
vector<int> regs[dydis];
int tevas[dydis];
vector<int> gr[dydis];
unordered_map<long long, long long > rem;
int sm[dydis];
int val[dydis];
int kam[dydis];
int sq;
int dbInd = 0;
int kelint[dydis];
int enter[dydis], leave[dydis];
vector<long long> dideliuMem1[dydis], dideliuMem2[dydis];

void dfs1(int v, int came){
	enter[v] = dbInd++;
	for(auto x : gr[v]){
		if(x == came) continue;
		dfs1(x, v);
	}
	leave[v] = dbInd;
}
bool isAnc(int a, int b){
	return enter[a] <= enter[b] && leave[b] <= leave[a];
}
void dfs(int v, int came, int kek, int prm){
//		cout << "v = " << v << endl;
	sm[v] = val[v];
	for(auto x : gr[v]){
		if(x == came) continue;
		dfs(x, v, kek + val[v], prm);
		sm[v] += sm[x];
	}

	if(!val[v]){
//		cout << "rem[" << prm+1 << "][" << v+1 << "(" << kam[v]+1 << ")] += " << kek << "\n";
//		cout << "rem[" << v+1 << "(" << kam[v]+1 << ")][" << prm+1 << "] += " << sm[v] << "\n"
		dideliuMem1[prm][kam[v]] += kek;
		dideliuMem2[prm][kam[v]] += sm[v];
	}
}
int kell = 0;
void calc(int ind){
	kelint[ind] = kell++;
	dideliuMem1[kelint[ind]].resize(r);
	dideliuMem2[kelint[ind]].resize(r);
//	cout << "nuo " << ind+1 << endl;
	for(int i = 0; i < n; i++) sm[i] = val[i] = 0;
	for(auto x : regs[ind]){
		val[x] = 1;
	}
	dfs(0, -1, 0, kelint[ind]);
}
long long f(int a, int b){
	if((int)regs[a].size() >= sq){
		int sk = kelint[a];
		return dideliuMem1[sk][b];
	}
	if((int)regs[b].size() >= sq){
		int sk = kelint[b];
		return dideliuMem2[sk][a];
	}
	if(rem.count(a * dydis + b)) {
		return rem[a * dydis + b] ;
	}
	long long ret = 0;
	for(auto x : regs[a]){
		for(auto y : regs[b]){
			ret += isAnc(x, y);
		}
	}
	return rem[a * dydis + b] = ret;
}
int main(){
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n >> r >> q;
	for(int i = 0; i < n; i++){
		int par = -1, reg;
		if(i == 0) cin >> reg;
		else cin >> par >> reg;
		par--; reg--;
		regs[reg].push_back(i);
		if(par != -2){
			gr[i].push_back(par);
			gr[par].push_back(i);
		}
		tevas[i] = par;
		kam[i] = reg;
	}
	dfs1(0, -1);
	sq = sqrt(n)-15;
	for(int i = 0; i < r; i++){
		if((int)regs[i].size() >= sq){
			calc(i);
			dideli.push_back(i);
		}
	}
	while(q--){
		int a, b; cin >> a >> b; a--; b--;
		cout << f(a, b) << endl;
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19016 KB Output is correct
2 Correct 11 ms 19016 KB Output is correct
3 Correct 13 ms 19016 KB Output is correct
4 Correct 19 ms 19092 KB Output is correct
5 Correct 15 ms 19144 KB Output is correct
6 Correct 28 ms 19224 KB Output is correct
7 Correct 50 ms 19252 KB Output is correct
8 Correct 46 ms 19300 KB Output is correct
9 Correct 41 ms 19788 KB Output is correct
10 Correct 130 ms 19944 KB Output is correct
11 Correct 266 ms 20228 KB Output is correct
12 Correct 195 ms 20908 KB Output is correct
13 Correct 340 ms 21100 KB Output is correct
14 Correct 592 ms 21408 KB Output is correct
15 Correct 659 ms 25392 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3221 ms 25764 KB Output is correct
2 Correct 3077 ms 25188 KB Output is correct
3 Execution timed out 8074 ms 29860 KB Time limit exceeded
4 Correct 360 ms 23804 KB Output is correct
5 Correct 522 ms 23792 KB Output is correct
6 Correct 685 ms 30536 KB Output is correct
7 Correct 1148 ms 32500 KB Output is correct
8 Correct 1323 ms 47496 KB Output is correct
9 Correct 6234 ms 33776 KB Output is correct
10 Correct 7042 ms 78712 KB Output is correct
11 Execution timed out 8005 ms 32888 KB Time limit exceeded
12 Correct 5420 ms 33120 KB Output is correct
13 Execution timed out 8037 ms 35464 KB Time limit exceeded
14 Correct 6785 ms 42176 KB Output is correct
15 Execution timed out 8068 ms 40596 KB Time limit exceeded
16 Execution timed out 8044 ms 49868 KB Time limit exceeded
17 Execution timed out 8058 ms 56480 KB Time limit exceeded