oj.uz

Submission #411519

# Submission time Handle Problem Language Result Execution time Memory
411519 2021-05-25T13:02:04 Z AugustinasJucas Regions (IOI09_regions) C++14
27 / 100
 8000 ms 68640 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
const int dydis = 2e5 + 1;
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 = ind;
	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
12.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9672 KB Output is correct
2 Incorrect 6 ms 9736 KB Output isn't correct
3 Correct 8 ms 9736 KB Output is correct
4 Correct 12 ms 9748 KB Output is correct
5 Correct 17 ms 9768 KB Output is correct
6 Correct 26 ms 9848 KB Output is correct
7 Correct 43 ms 9912 KB Output is correct
8 Correct 55 ms 10004 KB Output is correct
9 Correct 57 ms 10416 KB Output is correct
10 Correct 110 ms 10684 KB Output is correct
11 Correct 242 ms 11004 KB Output is correct
12 Correct 197 ms 11628 KB Output is correct
13 Correct 379 ms 11760 KB Output is correct
14 Incorrect 999 ms 12676 KB Output isn't correct
15 Incorrect 826 ms 15812 KB Output isn't correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 3384 ms 16868 KB Output isn't correct
2 Incorrect 5402 ms 16504 KB Output isn't correct
3 Execution timed out 8045 ms 21136 KB Time limit exceeded
4 Correct 473 ms 12992 KB Output is correct
5 Correct 570 ms 15016 KB Output is correct
6 Runtime error 52 ms 27056 KB Execution killed with signal 11
7 Runtime error 85 ms 30728 KB Execution killed with signal 11
8 Runtime error 106 ms 43516 KB Execution killed with signal 11
9 Correct 6960 ms 27180 KB Output is correct
10 Runtime error 114 ms 53472 KB Execution killed with signal 11
11 Execution timed out 8050 ms 24220 KB Time limit exceeded
12 Runtime error 133 ms 43396 KB Execution killed with signal 11
13 Runtime error 119 ms 44872 KB Execution killed with signal 11
14 Runtime error 187 ms 46880 KB Execution killed with signal 11
15 Runtime error 133 ms 51440 KB Execution killed with signal 11
16 Runtime error 152 ms 68640 KB Execution killed with signal 11
17 Runtime error 155 ms 66824 KB Execution killed with signal 11