oj.uz

Submission #411258

# Submission time Handle Problem Language Result Execution time Memory
411258 2021-05-24T20:52:27 Z AugustinasJucas Regions (IOI09_regions) C++14
65 / 100
 8000 ms 50260 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];
map<pair<int, int>, 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<vector<long long> > dideliuMem1, dideliuMem2;

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];
	}
}
void calc(int ind){
	kelint[ind] = dideliuMem1.size();
	dideliuMem1.push_back(vector<long long> (r, 0));
	dideliuMem2.push_back(vector<long long> (r, 0));
//	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, b})) {
		return rem[{a, b}] ;
	}
	long long ret = 0;
	for(auto x : regs[a]){
		for(auto y : regs[b]){
			ret += isAnc(x, y);
		}
	}
	return rem[{a, 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)+40;
	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 6 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 9 ms 9740 KB Output is correct
4 Correct 12 ms 9728 KB Output is correct
5 Correct 13 ms 9784 KB Output is correct
6 Correct 23 ms 9800 KB Output is correct
7 Correct 38 ms 9960 KB Output is correct
8 Correct 42 ms 10040 KB Output is correct
9 Correct 70 ms 10540 KB Output is correct
10 Correct 117 ms 10872 KB Output is correct
11 Correct 212 ms 11080 KB Output is correct
12 Correct 254 ms 11652 KB Output is correct
13 Correct 391 ms 11780 KB Output is correct
14 Correct 885 ms 12092 KB Output is correct
15 Correct 816 ms 14696 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3680 ms 16728 KB Output is correct
2 Correct 5073 ms 16368 KB Output is correct
3 Execution timed out 8038 ms 21740 KB Time limit exceeded
4 Correct 337 ms 13028 KB Output is correct
5 Correct 578 ms 15096 KB Output is correct
6 Correct 651 ms 21676 KB Output is correct
7 Correct 1114 ms 23400 KB Output is correct
8 Correct 1311 ms 38576 KB Output is correct
9 Correct 6664 ms 27188 KB Output is correct
10 Execution timed out 8021 ms 50260 KB Time limit exceeded
11 Execution timed out 8034 ms 24224 KB Time limit exceeded
12 Correct 5530 ms 24604 KB Output is correct
13 Execution timed out 8007 ms 27464 KB Time limit exceeded
14 Correct 6850 ms 34012 KB Output is correct
15 Execution timed out 8066 ms 32176 KB Time limit exceeded
16 Execution timed out 8026 ms 41492 KB Time limit exceeded
17 Execution timed out 8066 ms 47864 KB Time limit exceeded