oj.uz

Submission #411252

# Submission time Handle Problem Language Result Execution time Memory
411252 2021-05-24T20:33:32 Z AugustinasJucas Regions (IOI09_regions) C++14
30 / 100
 8000 ms 29480 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 enter[dydis], leave[dydis];
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";
		rem[{prm, kam[v]}] += kek;
		rem[{kam[v], prm}] += sm[v]; 
	}
}
void calc(int ind){
//	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, ind);
}
long long f(int a, int b){
	if(rem.count({a, b})) {
		long long dal = 1;
		if(regs[kam[a]].size() >= sq && regs[kam[b]].size() >= sq) dal = 2;
		return rem[{a, b}] / dal;
	}
	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);
		}
	}
	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:55:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |   if(regs[kam[a]].size() >= sq && regs[kam[b]].size() >= sq) dal = 2;
      |      ~~~~~~~~~~~~~~~~~~~~^~~~~
regions.cpp:55:55: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |   if(regs[kam[a]].size() >= sq && regs[kam[b]].size() >= sq) dal = 2;
      |                                   ~~~~~~~~~~~~~~~~~~~~^~~~~

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 10 ms 9672 KB Output is correct
4 Correct 11 ms 9736 KB Output is correct
5 Correct 16 ms 9788 KB Output is correct
6 Correct 32 ms 9800 KB Output is correct
7 Correct 38 ms 9956 KB Output is correct
8 Correct 44 ms 10036 KB Output is correct
9 Correct 74 ms 10372 KB Output is correct
10 Correct 135 ms 10712 KB Output is correct
11 Correct 214 ms 11036 KB Output is correct
12 Correct 222 ms 11580 KB Output is correct
13 Correct 326 ms 11820 KB Output is correct
14 Correct 940 ms 12128 KB Output is correct
15 Correct 758 ms 14240 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8071 ms 14740 KB Time limit exceeded
2 Execution timed out 8061 ms 14348 KB Time limit exceeded
3 Execution timed out 8039 ms 16088 KB Time limit exceeded
4 Correct 375 ms 13124 KB Output is correct
5 Correct 538 ms 14616 KB Output is correct
6 Incorrect 792 ms 14752 KB Output isn't correct
7 Incorrect 841 ms 15116 KB Output isn't correct
8 Incorrect 3275 ms 21484 KB Output isn't correct
9 Correct 6953 ms 26880 KB Output is correct
10 Execution timed out 8051 ms 24668 KB Time limit exceeded
11 Execution timed out 8038 ms 24208 KB Time limit exceeded
12 Execution timed out 8013 ms 21148 KB Time limit exceeded
13 Execution timed out 8103 ms 22052 KB Time limit exceeded
14 Execution timed out 8086 ms 21664 KB Time limit exceeded
15 Execution timed out 8070 ms 24380 KB Time limit exceeded
16 Execution timed out 8026 ms 29480 KB Time limit exceeded
17 Execution timed out 8073 ms 27576 KB Time limit exceeded