oj.uz

답안 #129958

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129958 2019-07-13T16:00:12 Z Markomafko972 Regions (IOI09_regions) C++14
1 / 100
 3974 ms 131076 KB 
#include <bits/stdc++.h>
#define X first
#define Y second
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;

int n, r, q, cv, q1, q2;
int sq;
vector<int> v[200002];
unordered_map<int, ll> m[25002];
int w[200002];
int kol[200002];
int kol2[200002];
vector<int> g[200002];
int t;
int d1[200002];
int d2[200002];

void dfs(int x) {
	for (int i = 0; i < v[x].size(); i ++) {
		int sus = v[x][i];
		dfs(sus);
		kol[x] += kol[sus];
	}
	
	//cout << "mapa od " << x << ", " << t << " += " << kol[x] << endl; 
	m[w[x]][t] += kol[x];
}

void rek(int x, int y) {
	y += kol2[x];
	m[t][w[x]] += y;
	for (int i = 0; i < v[x].size(); i ++) {
		rek(v[x][i], y);
	}
}

int tren;
void ord(int x) {
	tren ++;
	d1[x] = tren;
	for (int i = 0; i < v[x].size(); i ++) {
		ord(v[x][i]);
	}
	d2[x] = tren;
	//cout << x << ": " << d1[x] << " " << d2[x] << endl;
}

int main () {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> r >> q;
	sq = sqrt(n);
	cin >> w[1];
	g[w[1]].push_back(1);
	for (int i = 2; i <= n; i ++) {
		cin >> cv >> w[i];
		g[w[i]].push_back(i);
		v[cv].push_back(i);
	}
	
	ord(1);
	
	for (int i = 1; i <= r; i ++) {
		if (g[i].size() > sq) {
			memset(kol, 0, sizeof kol);
			memset(kol2, 0, sizeof kol2);
			t = i;
			for (int j = 0; j < g[i].size(); j ++) {
				kol[g[i][j]] = 1;
				kol2[g[i][j]] = 1;
			}
			
			dfs(1);
			rek(1, 0);
		}
	}
	
	for (int i = 0; i < q; i ++) {
		cin >> q1 >> q2;
		if (g[q1].size() > sq && g[q2].size() > sq) {
			m[q1][q2] /= 2;
		}
		
		if (g[q1].size() <= sq && g[q2].size() <= sq) {

		}
		
		cout << max(0LL, m[q1][q2]) << endl;
	}

	return 0;
}

Compilation message

regions.cpp: In function 'void dfs(int)':
regions.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v[x].size(); i ++) {
                  ~~^~~~~~~~~~~~~
regions.cpp: In function 'void rek(int, int)':
regions.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v[x].size(); i ++) {
                  ~~^~~~~~~~~~~~~
regions.cpp: In function 'void ord(int)':
regions.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v[x].size(); i ++) {
                  ~~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:69:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[i].size() > sq) {
       ~~~~~~~~~~~~^~~~
regions.cpp:73:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < g[i].size(); j ++) {
                    ~~^~~~~~~~~~~~~
regions.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() > sq && g[q2].size() > sq) {
       ~~~~~~~~~~~~~^~~~
regions.cpp:85:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() > sq && g[q2].size() > sq) {
                            ~~~~~~~~~~~~~^~~~
regions.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() <= sq && g[q2].size() <= sq) {
       ~~~~~~~~~~~~~^~~~~
regions.cpp:89:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() <= sq && g[q2].size() <= sq) {
                             ~~~~~~~~~~~~~^~~~~

Subtask #1
1.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12664 KB Output is correct
2 Incorrect 12 ms 11000 KB Output isn't correct
3 Incorrect 12 ms 11124 KB Output isn't correct
4 Incorrect 17 ms 11128 KB Output isn't correct
5 Incorrect 19 ms 11128 KB Output isn't correct
6 Incorrect 29 ms 11256 KB Output isn't correct
7 Incorrect 43 ms 11388 KB Output isn't correct
8 Incorrect 44 ms 11356 KB Output isn't correct
9 Incorrect 60 ms 11680 KB Output isn't correct
10 Incorrect 102 ms 11896 KB Output isn't correct
11 Incorrect 121 ms 12208 KB Output isn't correct
12 Incorrect 150 ms 12752 KB Output isn't correct
13 Incorrect 164 ms 12608 KB Output isn't correct
14 Incorrect 155 ms 14692 KB Output isn't correct
15 Incorrect 202 ms 17188 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1016 ms 18136 KB Output isn't correct
2 Incorrect 1137 ms 16788 KB Output isn't correct
3 Incorrect 1519 ms 21384 KB Output isn't correct
4 Incorrect 272 ms 13560 KB Output isn't correct
5 Incorrect 278 ms 15280 KB Output isn't correct
6 Incorrect 1618 ms 45860 KB Output isn't correct
7 Incorrect 2289 ms 59364 KB Output isn't correct
8 Incorrect 3407 ms 107404 KB Output isn't correct
9 Incorrect 1325 ms 24780 KB Output isn't correct
10 Runtime error 2714 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Incorrect 2001 ms 28036 KB Output isn't correct
12 Incorrect 964 ms 26480 KB Output isn't correct
13 Incorrect 1462 ms 27968 KB Output isn't correct
14 Incorrect 3974 ms 57964 KB Output isn't correct
15 Incorrect 2198 ms 35852 KB Output isn't correct
16 Incorrect 2196 ms 40572 KB Output isn't correct
17 Incorrect 3173 ms 70260 KB Output isn't correct