oj.uz

답안 #1109426

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1109426 2024-11-06T16:24:55 Z sano Regions (IOI09_regions) C++14
0 / 100
 108 ms 54056 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);
	For(i, reg.size()) {
		s_n[e[reg[i][0]]] = i;
	}
	return 0;
	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 Runtime error 1 ms 336 KB Execution killed with signal 11
2 Runtime error 1 ms 592 KB Execution killed with signal 11
3 Runtime error 1 ms 592 KB Execution killed with signal 11
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 Runtime error 2 ms 592 KB Execution killed with signal 11
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 1636 KB Unexpected end of file - int32 expected
12 Incorrect 8 ms 2128 KB Unexpected end of file - int32 expected
13 Incorrect 6 ms 2384 KB Unexpected end of file - int32 expected
14 Incorrect 9 ms 2916 KB Unexpected end of file - int32 expected
15 Incorrect 11 ms 5516 KB Unexpected end of file - int32 expected

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 6984 KB Unexpected end of file - int32 expected
2 Incorrect 20 ms 6728 KB Unexpected end of file - int32 expected
3 Incorrect 23 ms 8896 KB Unexpected end of file - int32 expected
4 Runtime error 14 ms 6224 KB Execution killed with signal 11
5 Runtime error 20 ms 9552 KB Execution killed with signal 11
6 Runtime error 25 ms 10284 KB Execution killed with signal 11
7 Runtime error 32 ms 13648 KB Execution killed with signal 11
8 Runtime error 45 ms 24412 KB Execution killed with signal 11
9 Runtime error 65 ms 29524 KB Execution killed with signal 11
10 Runtime error 87 ms 40492 KB Execution killed with signal 11
11 Runtime error 91 ms 37388 KB Execution killed with signal 11
12 Runtime error 90 ms 33096 KB Execution killed with signal 11
13 Runtime error 75 ms 34632 KB Execution killed with signal 11
14 Runtime error 108 ms 36168 KB Execution killed with signal 11
15 Runtime error 91 ms 43080 KB Execution killed with signal 11
16 Runtime error 100 ms 54056 KB Execution killed with signal 11
17 Runtime error 96 ms 51192 KB Execution killed with signal 11