oj.uz

답안 #411255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411255 2021-05-24T20:40:03 Z AugustinasJucas Regions (IOI09_regions) C++14
55 / 100
 8000 ms 131076 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[a].size() >= sq && regs[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:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |   if(regs[a].size() >= sq && regs[b].size() >= sq) dal = 2;
      |      ~~~~~~~~~~~~~~~^~~~~
regions.cpp:55:45: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |   if(regs[a].size() >= sq && regs[b].size() >= sq) dal = 2;
      |                              ~~~~~~~~~~~~~~~^~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 8 ms 9736 KB Output is correct
4 Correct 9 ms 9672 KB Output is correct
5 Correct 16 ms 9760 KB Output is correct
6 Correct 15 ms 9868 KB Output is correct
7 Correct 35 ms 9860 KB Output is correct
8 Correct 47 ms 10048 KB Output is correct
9 Correct 79 ms 10432 KB Output is correct
10 Correct 134 ms 10708 KB Output is correct
11 Correct 204 ms 11304 KB Output is correct
12 Correct 236 ms 11624 KB Output is correct
13 Correct 412 ms 11836 KB Output is correct
14 Correct 954 ms 12592 KB Output is correct
15 Correct 834 ms 17636 KB Output is correct

Subtask #2
40.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3538 ms 17776 KB Output is correct
2 Correct 4992 ms 16884 KB Output is correct
3 Execution timed out 8038 ms 23252 KB Time limit exceeded
4 Correct 369 ms 12940 KB Output is correct
5 Correct 507 ms 14768 KB Output is correct
6 Correct 2778 ms 61088 KB Output is correct
7 Correct 4360 ms 78260 KB Output is correct
8 Runtime error 5962 ms 131076 KB Execution killed with signal 9
9 Correct 6117 ms 26876 KB Output is correct
10 Runtime error 4051 ms 131076 KB Execution killed with signal 9
11 Execution timed out 8074 ms 24296 KB Time limit exceeded
12 Correct 5426 ms 27764 KB Output is correct
13 Execution timed out 8064 ms 31244 KB Time limit exceeded
14 Execution timed out 8055 ms 73044 KB Time limit exceeded
15 Execution timed out 8006 ms 39992 KB Time limit exceeded
16 Execution timed out 8045 ms 52824 KB Time limit exceeded
17 Execution timed out 8023 ms 93916 KB Time limit exceeded