oj.uz

Submission #411256

# Submission time Handle Problem Language Result Execution time Memory
411256 2021-05-24T20:47:23 Z AugustinasJucas Regions (IOI09_regions) C++14
70 / 100
 8000 ms 70832 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
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 8 ms 9672 KB Output is correct
4 Correct 9 ms 9672 KB Output is correct
5 Correct 15 ms 9672 KB Output is correct
6 Correct 16 ms 9880 KB Output is correct
7 Correct 38 ms 9916 KB Output is correct
8 Correct 52 ms 10048 KB Output is correct
9 Correct 72 ms 10336 KB Output is correct
10 Correct 149 ms 10696 KB Output is correct
11 Correct 228 ms 11072 KB Output is correct
12 Correct 233 ms 11692 KB Output is correct
13 Correct 402 ms 11780 KB Output is correct
14 Correct 864 ms 12484 KB Output is correct
15 Correct 985 ms 16180 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3164 ms 16860 KB Output is correct
2 Correct 5191 ms 16408 KB Output is correct
3 Execution timed out 8061 ms 21692 KB Time limit exceeded
4 Correct 407 ms 13040 KB Output is correct
5 Correct 493 ms 14656 KB Output is correct
6 Correct 820 ms 21716 KB Output is correct
7 Correct 1151 ms 23704 KB Output is correct
8 Correct 1420 ms 38548 KB Output is correct
9 Correct 6573 ms 27132 KB Output is correct
10 Correct 6907 ms 70832 KB Output is correct
11 Execution timed out 8004 ms 24164 KB Time limit exceeded
12 Correct 5378 ms 24648 KB Output is correct
13 Execution timed out 8058 ms 27404 KB Time limit exceeded
14 Correct 6708 ms 33980 KB Output is correct
15 Execution timed out 8031 ms 32324 KB Time limit exceeded
16 Execution timed out 8007 ms 41424 KB Time limit exceeded
17 Execution timed out 8076 ms 48376 KB Time limit exceeded