oj.uz

Submission #411251

# Submission time Handle Problem Language Result Execution time Memory
411251 2021-05-24T20:29:54 Z AugustinasJucas Regions (IOI09_regions) C++14
28 / 100
 8000 ms 131076 KB 
#include <bits/stdc++.h>
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:54:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |   if(regs[kam[a]].size() >= sq && regs[kam[b]].size() >= sq) dal = 2;
      |      ~~~~~~~~~~~~~~~~~~~~^~~~~
regions.cpp:54:55: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |   if(regs[kam[a]].size() >= sq && regs[kam[b]].size() >= sq) dal = 2;
      |                                   ~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9604 KB Output is correct
2 Incorrect 7 ms 9672 KB Output isn't correct
3 Correct 8 ms 9676 KB Output is correct
4 Correct 12 ms 9672 KB Output is correct
5 Correct 16 ms 9768 KB Output is correct
6 Correct 24 ms 9872 KB Output is correct
7 Correct 46 ms 9920 KB Output is correct
8 Correct 53 ms 9952 KB Output is correct
9 Correct 62 ms 10492 KB Output is correct
10 Correct 108 ms 10680 KB Output is correct
11 Correct 175 ms 10996 KB Output is correct
12 Correct 217 ms 11728 KB Output is correct
13 Correct 419 ms 11904 KB Output is correct
14 Incorrect 870 ms 12612 KB Output isn't correct
15 Correct 960 ms 17600 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 3594 ms 17716 KB Output isn't correct
2 Incorrect 5090 ms 17068 KB Output isn't correct
3 Execution timed out 8082 ms 22844 KB Time limit exceeded
4 Correct 350 ms 13020 KB Output is correct
5 Correct 535 ms 15108 KB Output is correct
6 Incorrect 2875 ms 60936 KB Output isn't correct
7 Incorrect 4384 ms 78224 KB Output isn't correct
8 Runtime error 6083 ms 131076 KB Execution killed with signal 9
9 Correct 6806 ms 27204 KB Output is correct
10 Runtime error 4155 ms 131076 KB Execution killed with signal 9
11 Execution timed out 8090 ms 24416 KB Time limit exceeded
12 Incorrect 5479 ms 27776 KB Output isn't correct
13 Execution timed out 8003 ms 31160 KB Time limit exceeded
14 Execution timed out 8009 ms 73188 KB Time limit exceeded
15 Execution timed out 8006 ms 40004 KB Time limit exceeded
16 Execution timed out 8083 ms 52988 KB Time limit exceeded
17 Execution timed out 8026 ms 93968 KB Time limit exceeded