oj.uz

Submission #411518

# Submission time Handle Problem Language Result Execution time Memory
411518 2021-05-25T12:59:13 Z AugustinasJucas Regions (IOI09_regions) C++14
65 / 100
 8000 ms 62656 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];
long long dideliuMem1[450][20001], dideliuMem2[450][20001];
 
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 dbIndd = 0;
void calc(int ind){
	kelint[ind] = dbIndd++;
//	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);
	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 9740 KB Output is correct
4 Correct 13 ms 9684 KB Output is correct
5 Correct 15 ms 9776 KB Output is correct
6 Correct 25 ms 9868 KB Output is correct
7 Correct 49 ms 9920 KB Output is correct
8 Correct 39 ms 9920 KB Output is correct
9 Correct 68 ms 10524 KB Output is correct
10 Correct 141 ms 10688 KB Output is correct
11 Correct 202 ms 11072 KB Output is correct
12 Correct 213 ms 11716 KB Output is correct
13 Correct 394 ms 11820 KB Output is correct
14 Correct 963 ms 12528 KB Output is correct
15 Correct 875 ms 16272 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3467 ms 16912 KB Output is correct
2 Correct 5167 ms 16496 KB Output is correct
3 Execution timed out 8042 ms 21600 KB Time limit exceeded
4 Correct 390 ms 13024 KB Output is correct
5 Correct 606 ms 15036 KB Output is correct
6 Correct 701 ms 22176 KB Output is correct
7 Correct 1153 ms 24080 KB Output is correct
8 Correct 1306 ms 39456 KB Output is correct
9 Correct 6825 ms 27248 KB Output is correct
10 Incorrect 7332 ms 62656 KB Output isn't correct
11 Execution timed out 8042 ms 24360 KB Time limit exceeded
12 Correct 5397 ms 24736 KB Output is correct
13 Execution timed out 8016 ms 27544 KB Time limit exceeded
14 Correct 7213 ms 34064 KB Output is correct
15 Execution timed out 8084 ms 32060 KB Time limit exceeded
16 Execution timed out 8021 ms 41124 KB Time limit exceeded
17 Execution timed out 8044 ms 48196 KB Time limit exceeded