oj.uz

Submission #411263

# Submission time Handle Problem Language Result Execution time Memory
411263 2021-05-24T21:02:37 Z AugustinasJucas Regions (IOI09_regions) C++14
75 / 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) << endl;
	}
	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 12 ms 19132 KB Output is correct
3 Correct 14 ms 19016 KB Output is correct
4 Correct 17 ms 19016 KB Output is correct
5 Correct 15 ms 19168 KB Output is correct
6 Correct 24 ms 19288 KB Output is correct
7 Correct 49 ms 19228 KB Output is correct
8 Correct 56 ms 19260 KB Output is correct
9 Correct 50 ms 19788 KB Output is correct
10 Correct 138 ms 20020 KB Output is correct
11 Correct 242 ms 20276 KB Output is correct
12 Correct 268 ms 20840 KB Output is correct
13 Correct 414 ms 20956 KB Output is correct
14 Correct 955 ms 21676 KB Output is correct
15 Correct 855 ms 25472 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3454 ms 25832 KB Output is correct
2 Correct 5110 ms 25308 KB Output is correct
3 Execution timed out 8032 ms 29760 KB Time limit exceeded
4 Correct 337 ms 21940 KB Output is correct
5 Correct 418 ms 23644 KB Output is correct
6 Correct 751 ms 30524 KB Output is correct
7 Correct 1044 ms 32552 KB Output is correct
8 Correct 1215 ms 47484 KB Output is correct
9 Correct 6693 ms 33920 KB Output is correct
10 Correct 6831 ms 78716 KB Output is correct
11 Execution timed out 8058 ms 32860 KB Time limit exceeded
12 Correct 5436 ms 33248 KB Output is correct
13 Correct 7645 ms 35476 KB Output is correct
14 Correct 6559 ms 42056 KB Output is correct
15 Execution timed out 8045 ms 40556 KB Time limit exceeded
16 Execution timed out 8090 ms 49744 KB Time limit exceeded
17 Execution timed out 8018 ms 56436 KB Time limit exceeded