oj.uz

Submission #411257

# Submission time Handle Problem Language Result Execution time Memory
411257 2021-05-24T20:48:39 Z AugustinasJucas Regions (IOI09_regions) C++14
75 / 100
 8000 ms 70584 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<vector<long long> > dideliuMem1, dideliuMem2;

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];
	}
}
void calc(int ind){
	kelint[ind] = dideliuMem1.size();
	dideliuMem1.push_back(vector<long long> (r, 0));
	dideliuMem2.push_back(vector<long long> (r, 0));
//	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(regs[a].size() >= sq){
		int sk = kelint[a];
		return dideliuMem1[sk][b];
	}
	if(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;
}

Compilation message

regions.cpp: In function 'long long int f(int, int)':
regions.cpp:59:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |  if(regs[a].size() >= sq){
      |     ~~~~~~~~~~~~~~~^~~~~
regions.cpp:63:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |  if(regs[b].size() >= sq){
      |     ~~~~~~~~~~~~~~~^~~~~

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 9 ms 9672 KB Output is correct
4 Correct 9 ms 9744 KB Output is correct
5 Correct 14 ms 9768 KB Output is correct
6 Correct 20 ms 9944 KB Output is correct
7 Correct 54 ms 10048 KB Output is correct
8 Correct 49 ms 10016 KB Output is correct
9 Correct 42 ms 10488 KB Output is correct
10 Correct 133 ms 10660 KB Output is correct
11 Correct 245 ms 11096 KB Output is correct
12 Correct 241 ms 11640 KB Output is correct
13 Correct 408 ms 11828 KB Output is correct
14 Correct 906 ms 12332 KB Output is correct
15 Correct 790 ms 16256 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3215 ms 16708 KB Output is correct
2 Correct 5222 ms 16316 KB Output is correct
3 Execution timed out 8079 ms 21372 KB Time limit exceeded
4 Correct 347 ms 12992 KB Output is correct
5 Correct 560 ms 15140 KB Output is correct
6 Correct 641 ms 21608 KB Output is correct
7 Correct 1252 ms 23568 KB Output is correct
8 Correct 1388 ms 38500 KB Output is correct
9 Correct 6464 ms 27352 KB Output is correct
10 Correct 6619 ms 70584 KB Output is correct
11 Execution timed out 8069 ms 24380 KB Time limit exceeded
12 Correct 5564 ms 24576 KB Output is correct
13 Correct 7839 ms 27428 KB Output is correct
14 Correct 6594 ms 34304 KB Output is correct
15 Execution timed out 8022 ms 32612 KB Time limit exceeded
16 Execution timed out 8032 ms 41356 KB Time limit exceeded
17 Execution timed out 8039 ms 48276 KB Time limit exceeded