oj.uz

Submission #411524

# Submission time Handle Problem Language Result Execution time Memory
411524 2021-05-25T13:07:48 Z AugustinasJucas Regions (IOI09_regions) C++14
65 / 100
 8000 ms 61240 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("O2")
//#pragma GCC optimize("avx2")
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];
}
int kek = 0;
int prm = 0;
void dfs(int v){
//		cout << "v = " << v << endl;
	sm[v] = val[v];
	for(auto x : gr[v]){
		if(x == tevas[v]) continue;
		kek += val[v];
        dfs(x);
        kek -= val[v];
		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;
	}
    kek = 0;
    prm = dbIndd-1;
	dfs(0);
}
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 7 ms 9672 KB Output is correct
2 Correct 8 ms 9672 KB Output is correct
3 Correct 9 ms 9672 KB Output is correct
4 Correct 9 ms 9740 KB Output is correct
5 Correct 17 ms 9764 KB Output is correct
6 Correct 34 ms 9836 KB Output is correct
7 Correct 48 ms 9968 KB Output is correct
8 Correct 52 ms 10004 KB Output is correct
9 Correct 53 ms 10524 KB Output is correct
10 Correct 129 ms 10692 KB Output is correct
11 Correct 207 ms 11072 KB Output is correct
12 Correct 220 ms 11732 KB Output is correct
13 Correct 461 ms 11824 KB Output is correct
14 Correct 861 ms 12368 KB Output is correct
15 Correct 904 ms 15592 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3616 ms 16672 KB Output is correct
2 Correct 5465 ms 16408 KB Output is correct
3 Execution timed out 8058 ms 20920 KB Time limit exceeded
4 Correct 443 ms 13028 KB Output is correct
5 Correct 480 ms 15012 KB Output is correct
6 Correct 870 ms 22084 KB Output is correct
7 Correct 1045 ms 23932 KB Output is correct
8 Correct 1069 ms 38276 KB Output is correct
9 Correct 6486 ms 27148 KB Output is correct
10 Incorrect 6863 ms 61240 KB Output isn't correct
11 Execution timed out 8071 ms 24208 KB Time limit exceeded
12 Correct 5393 ms 24648 KB Output is correct
13 Execution timed out 8026 ms 27096 KB Time limit exceeded
14 Correct 7010 ms 33616 KB Output is correct
15 Execution timed out 8069 ms 31284 KB Time limit exceeded
16 Execution timed out 8044 ms 38224 KB Time limit exceeded
17 Execution timed out 8042 ms 45068 KB Time limit exceeded