oj.uz

Submission #411521

# Submission time Handle Problem Language Result Execution time Memory
411521 2021-05-25T13:05:09 Z AugustinasJucas Regions (IOI09_regions) C++14
65 / 100
 8000 ms 61292 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];
}
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 6 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 8 ms 9672 KB Output is correct
4 Correct 9 ms 9744 KB Output is correct
5 Correct 14 ms 9776 KB Output is correct
6 Correct 33 ms 9920 KB Output is correct
7 Correct 38 ms 9952 KB Output is correct
8 Correct 42 ms 10036 KB Output is correct
9 Correct 58 ms 10428 KB Output is correct
10 Correct 123 ms 10808 KB Output is correct
11 Correct 236 ms 11068 KB Output is correct
12 Correct 261 ms 11700 KB Output is correct
13 Correct 444 ms 11776 KB Output is correct
14 Correct 858 ms 12488 KB Output is correct
15 Correct 799 ms 15648 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3222 ms 16912 KB Output is correct
2 Correct 5341 ms 16404 KB Output is correct
3 Execution timed out 8032 ms 20872 KB Time limit exceeded
4 Correct 444 ms 13144 KB Output is correct
5 Correct 504 ms 15092 KB Output is correct
6 Correct 725 ms 22072 KB Output is correct
7 Correct 1242 ms 23780 KB Output is correct
8 Correct 1437 ms 38260 KB Output is correct
9 Correct 7138 ms 27228 KB Output is correct
10 Incorrect 7100 ms 61292 KB Output isn't correct
11 Execution timed out 8090 ms 24180 KB Time limit exceeded
12 Correct 5542 ms 24776 KB Output is correct
13 Execution timed out 8068 ms 27232 KB Time limit exceeded
14 Correct 7030 ms 33792 KB Output is correct
15 Execution timed out 8029 ms 31104 KB Time limit exceeded
16 Execution timed out 8028 ms 38360 KB Time limit exceeded
17 Execution timed out 8052 ms 44980 KB Time limit exceeded