oj.uz

Submission #411259

# Submission time Handle Problem Language Result Execution time Memory
411259 2021-05-24T20:53:21 Z AugustinasJucas Regions (IOI09_regions) C++14
70 / 100
 8000 ms 70700 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 9692 KB Output is correct
3 Correct 10 ms 9672 KB Output is correct
4 Correct 13 ms 9692 KB Output is correct
5 Correct 18 ms 9740 KB Output is correct
6 Correct 24 ms 10868 KB Output is correct
7 Correct 43 ms 10092 KB Output is correct
8 Correct 56 ms 10440 KB Output is correct
9 Correct 86 ms 10488 KB Output is correct
10 Correct 106 ms 10740 KB Output is correct
11 Correct 244 ms 11092 KB Output is correct
12 Correct 260 ms 11764 KB Output is correct
13 Correct 436 ms 11856 KB Output is correct
14 Correct 398 ms 12268 KB Output is correct
15 Correct 339 ms 16168 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3485 ms 16732 KB Output is correct
2 Correct 2052 ms 15492 KB Output is correct
3 Execution timed out 8012 ms 21392 KB Time limit exceeded
4 Correct 405 ms 17888 KB Output is correct
5 Correct 489 ms 15236 KB Output is correct
6 Correct 686 ms 21636 KB Output is correct
7 Correct 1357 ms 23528 KB Output is correct
8 Correct 1306 ms 38512 KB Output is correct
9 Correct 6951 ms 27140 KB Output is correct
10 Correct 7033 ms 70700 KB Output is correct
11 Execution timed out 8042 ms 24264 KB Time limit exceeded
12 Correct 5434 ms 24620 KB Output is correct
13 Execution timed out 8061 ms 27488 KB Time limit exceeded
14 Correct 6607 ms 34164 KB Output is correct
15 Execution timed out 8016 ms 32328 KB Time limit exceeded
16 Execution timed out 8007 ms 41712 KB Time limit exceeded
17 Execution timed out 8039 ms 48388 KB Time limit exceeded