oj.uz

Submission #411261

# Submission time Handle Problem Language Result Execution time Memory
411261 2021-05-24T20:59:23 Z AugustinasJucas Regions (IOI09_regions) C++14
75 / 100
 8000 ms 79960 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<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, 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 12 ms 19016 KB Output is correct
2 Correct 11 ms 19016 KB Output is correct
3 Correct 15 ms 19016 KB Output is correct
4 Correct 16 ms 19144 KB Output is correct
5 Correct 21 ms 19092 KB Output is correct
6 Correct 36 ms 19264 KB Output is correct
7 Correct 40 ms 19352 KB Output is correct
8 Correct 52 ms 19520 KB Output is correct
9 Correct 70 ms 19888 KB Output is correct
10 Correct 133 ms 20016 KB Output is correct
11 Correct 161 ms 20380 KB Output is correct
12 Correct 226 ms 21040 KB Output is correct
13 Correct 412 ms 21196 KB Output is correct
14 Correct 579 ms 21624 KB Output is correct
15 Correct 828 ms 25596 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3152 ms 26064 KB Output is correct
2 Correct 3282 ms 25276 KB Output is correct
3 Execution timed out 8068 ms 30988 KB Time limit exceeded
4 Correct 373 ms 24168 KB Output is correct
5 Correct 473 ms 24468 KB Output is correct
6 Correct 676 ms 31032 KB Output is correct
7 Correct 1121 ms 32900 KB Output is correct
8 Correct 1241 ms 48140 KB Output is correct
9 Correct 6719 ms 36540 KB Output is correct
10 Correct 6580 ms 79960 KB Output is correct
11 Execution timed out 8035 ms 33648 KB Time limit exceeded
12 Correct 5369 ms 34000 KB Output is correct
13 Correct 7866 ms 36924 KB Output is correct
14 Correct 6675 ms 43540 KB Output is correct
15 Execution timed out 8041 ms 41752 KB Time limit exceeded
16 Execution timed out 8058 ms 50852 KB Time limit exceeded
17 Execution timed out 8018 ms 57732 KB Time limit exceeded