oj.uz

답안 #1109425

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109425 2024-11-06T16:24:07 Z sano Regions (IOI09_regions) C++14
0 / 100
 92 ms 26696 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#define ll long long
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define shit short double
#define pii pair<int, int>
#define NEK 2147483640
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8

using namespace std;

vec<vec<int>> g;
vec<int> eul1, eul2;
vec<vec<int>> odp;
vec<int> e;
vec<vec<int>> m;
int ti = 0;

void DFS(int x, int pr) {
	eul1[x] = ti; ti++; m[e[x]].push_back(eul1[x]);
	for (auto i : g[x]) {
		if (i == pr) continue;
		DFS(i, x);
	}
	eul2[x] = ti - 1;
	return;
}

bool zorad(vec<int>& a, vec<int>& b) {
	return a.size() > b.size();
}

void DFS2(int x, int pr, int k, int v = 0) {
	if (e[x] == k) v++;
	odp.back()[e[x]] += v;
	for (auto i : g[x]) {
		if (i == pr) continue;
		DFS2(i, x, k, v);
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	//ifstream cin("promote.in");
	//ofstream cout("promote.out");
	int n, r, q;
	cin >> n >> r >> q;
	vec<vec<int>> reg(r);
	g.resize(n); eul1.resize(n); eul2.resize(n);
	e.resize(n);
	cin >> e[0]; e[0]--;
	reg[e[0]].push_back(0);
	ffor(i, 1, n) {
		int x; cin >> x; x--;
		g[x].push_back(i);
		g[i].push_back(x);
		cin >> e[i]; e[i]--;
		reg[e[i]].push_back(i);
	}
	m.resize(r);
	DFS(0, -1);

	sort(reg.begin(), reg.end(), zorad);
	vec<int> s_n(r, -1);
	return 0;
	For(i, reg.size()) {
		s_n[e[reg[i][0]]] = i;
	}
	int odm = sqrt(n);
	vec<int> trol(r, 0);
	For(i, reg.size()) {
		if (reg[i].size() >= odm) {
			odp.push_back(trol);
			DFS2(0, -1, e[reg[i][0]]);
		}
	}
	For(i, m.size()) {
		sort(m[i].begin(), m[i].end());
	}
	For(i, q) {
		int r1, r2; cin >> r1 >> r2; r1--; r2--;
		if (s_n[r1] == -1) {
			cout << 0 << endl;
		}
		if (s_n[r1] >= odp.size()) {
			int vys = 0;
			for (auto i : reg[s_n[r1]]) {
				int q1 = lower_bound(m[r2].begin(), m[r2].end(), eul1[i]) - m[r2].begin();
				int q2 = upper_bound(m[r2].begin(), m[r2].end(), eul2[i]) - m[r2].begin();
				vys += q2 - q1;
			}
			cout << vys << endl;
		}
		else {
			cout << odp[s_n[r1]][r2] << endl;
		}
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:97:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |   if (reg[i].size() >= odm) {
      |       ~~~~~~~~~~~~~~^~~~~~
regions.cpp:110:15: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   if (s_n[r1] >= odp.size()) {

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 336 KB Unexpected end of file - int32 expected
2 Incorrect 1 ms 336 KB Unexpected end of file - int32 expected
3 Incorrect 1 ms 336 KB Unexpected end of file - int32 expected
4 Incorrect 1 ms 336 KB Unexpected end of file - int32 expected
5 Incorrect 1 ms 336 KB Unexpected end of file - int32 expected
6 Incorrect 1 ms 336 KB Unexpected end of file - int32 expected
7 Incorrect 1 ms 592 KB Unexpected end of file - int32 expected
8 Incorrect 2 ms 592 KB Unexpected end of file - int32 expected
9 Incorrect 2 ms 1104 KB Unexpected end of file - int32 expected
10 Incorrect 3 ms 1104 KB Unexpected end of file - int32 expected
11 Incorrect 5 ms 1616 KB Unexpected end of file - int32 expected
12 Incorrect 7 ms 2128 KB Unexpected end of file - int32 expected
13 Incorrect 7 ms 2384 KB Unexpected end of file - int32 expected
14 Incorrect 9 ms 2896 KB Unexpected end of file - int32 expected
15 Incorrect 12 ms 5456 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 6736 KB Unexpected end of file - int32 expected
2 Incorrect 20 ms 6736 KB Unexpected end of file - int32 expected
3 Incorrect 32 ms 8892 KB Unexpected end of file - int32 expected
4 Incorrect 10 ms 3152 KB Unexpected end of file - int32 expected
5 Incorrect 12 ms 4856 KB Unexpected end of file - int32 expected
6 Incorrect 21 ms 5156 KB Unexpected end of file - int32 expected
7 Incorrect 23 ms 6984 KB Unexpected end of file - int32 expected
8 Incorrect 29 ms 12112 KB Unexpected end of file - int32 expected
9 Incorrect 48 ms 14368 KB Unexpected end of file - int32 expected
10 Incorrect 55 ms 20040 KB Unexpected end of file - int32 expected
11 Incorrect 92 ms 18584 KB Unexpected end of file - int32 expected
12 Incorrect 61 ms 16424 KB Unexpected end of file - int32 expected
13 Incorrect 60 ms 17224 KB Unexpected end of file - int32 expected
14 Incorrect 66 ms 17960 KB Unexpected end of file - int32 expected
15 Incorrect 65 ms 21320 KB Unexpected end of file - int32 expected
16 Incorrect 69 ms 26696 KB Unexpected end of file - int32 expected
17 Incorrect 82 ms 25268 KB Unexpected end of file - int32 expected