oj.uz

Submission #411517

# Submission time Handle Problem Language Result Execution time Memory
411517 2021-05-25T12:56:48 Z AugustinasJucas Regions (IOI09_regions) C++14
70 / 100
 8000 ms 78716 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);
	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) << "\n" << flush;
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19016 KB Output is correct
2 Correct 14 ms 19016 KB Output is correct
3 Correct 17 ms 19016 KB Output is correct
4 Correct 19 ms 19128 KB Output is correct
5 Correct 17 ms 19152 KB Output is correct
6 Correct 38 ms 19260 KB Output is correct
7 Correct 26 ms 19272 KB Output is correct
8 Correct 56 ms 19424 KB Output is correct
9 Correct 69 ms 19764 KB Output is correct
10 Correct 89 ms 20024 KB Output is correct
11 Correct 235 ms 20296 KB Output is correct
12 Correct 262 ms 20916 KB Output is correct
13 Correct 429 ms 20980 KB Output is correct
14 Correct 969 ms 21592 KB Output is correct
15 Correct 939 ms 25372 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3383 ms 25844 KB Output is correct
2 Correct 5469 ms 25352 KB Output is correct
3 Execution timed out 8015 ms 29836 KB Time limit exceeded
4 Correct 276 ms 21980 KB Output is correct
5 Correct 562 ms 23616 KB Output is correct
6 Correct 912 ms 30488 KB Output is correct
7 Correct 1184 ms 32476 KB Output is correct
8 Correct 1535 ms 47508 KB Output is correct
9 Correct 6745 ms 33880 KB Output is correct
10 Correct 6893 ms 78716 KB Output is correct
11 Execution timed out 8057 ms 32784 KB Time limit exceeded
12 Correct 5843 ms 33084 KB Output is correct
13 Execution timed out 8060 ms 35412 KB Time limit exceeded
14 Correct 7109 ms 41940 KB Output is correct
15 Execution timed out 8045 ms 40416 KB Time limit exceeded
16 Execution timed out 8020 ms 49560 KB Time limit exceeded
17 Execution timed out 8020 ms 55188 KB Time limit exceeded