oj.uz

Submission #411260

# Submission time Handle Problem Language Result Execution time Memory
411260 2021-05-24T20:56:21 Z AugustinasJucas Regions (IOI09_regions) C++14
75 / 100
 8000 ms 70584 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)-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 6 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 8 ms 9672 KB Output is correct
4 Correct 12 ms 9672 KB Output is correct
5 Correct 14 ms 9716 KB Output is correct
6 Correct 33 ms 9800 KB Output is correct
7 Correct 36 ms 9988 KB Output is correct
8 Correct 41 ms 10100 KB Output is correct
9 Correct 39 ms 10484 KB Output is correct
10 Correct 125 ms 10692 KB Output is correct
11 Correct 150 ms 11016 KB Output is correct
12 Correct 189 ms 11692 KB Output is correct
13 Correct 429 ms 11796 KB Output is correct
14 Correct 634 ms 12176 KB Output is correct
15 Correct 789 ms 16376 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3364 ms 16800 KB Output is correct
2 Correct 3380 ms 15820 KB Output is correct
3 Execution timed out 8077 ms 21712 KB Time limit exceeded
4 Correct 360 ms 14752 KB Output is correct
5 Correct 361 ms 15060 KB Output is correct
6 Correct 817 ms 21696 KB Output is correct
7 Correct 1235 ms 23492 KB Output is correct
8 Correct 1444 ms 38576 KB Output is correct
9 Correct 7016 ms 27272 KB Output is correct
10 Correct 6641 ms 70584 KB Output is correct
11 Execution timed out 8036 ms 24304 KB Time limit exceeded
12 Correct 5456 ms 24676 KB Output is correct
13 Correct 7905 ms 27428 KB Output is correct
14 Correct 6575 ms 34108 KB Output is correct
15 Execution timed out 8074 ms 32240 KB Time limit exceeded
16 Execution timed out 8070 ms 41808 KB Time limit exceeded
17 Execution timed out 8068 ms 48676 KB Time limit exceeded