답안 #129883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129883 2019-07-13T12:50:09 Z Markomafko972 Regions (IOI09_regions) C++14
4 / 100
8000 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, int> 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 loga[200002];

void update(int x, int y) {
	for (x; x <= n; x += x & -x) loga[x] += y;
}

int query(int x) {
	int out = 0;
	for (x; x > 0; x -= x & -x) out += loga[x];
	return out;
}

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 && m[q1][q2] == 0) {
			for (int j = 0; j < g[q2].size(); j ++) {
				update(g[q2][j], 1);
			}
			
			for (int j = 0; j < g[q1].size(); j ++) {
				m[q1][q2] += query(d2[ g[q1][j] ]);
				m[q1][q2] -= query(d1[ g[q1][j] ]-1);
			}
			
			for (int j = 0; j < g[q2].size(); j ++) {
				update(g[q2][j], -1);
			}
			
			if (m[q1][q2] == 0) m[q1][q2] = -1;
		}
		
		cout << max(0, 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 'void update(int, int)':
regions.cpp:55:8: warning: statement has no effect [-Wunused-value]
  for (x; x <= n; x += x & -x) loga[x] += y;
        ^
regions.cpp: In function 'int query(int)':
regions.cpp:60:8: warning: statement has no effect [-Wunused-value]
  for (x; x > 0; x -= x & -x) out += loga[x];
        ^
regions.cpp: In function 'int main()':
regions.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[i].size() > sq) {
       ~~~~~~~~~~~~^~~~
regions.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < g[i].size(); j ++) {
                    ~~^~~~~~~~~~~~~
regions.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() > sq && g[q2].size() > sq) {
       ~~~~~~~~~~~~~^~~~
regions.cpp:97:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() > sq && g[q2].size() > sq) {
                            ~~~~~~~~~~~~~^~~~
regions.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() <= sq && g[q2].size() <= sq && m[q1][q2] == 0) {
       ~~~~~~~~~~~~~^~~~~
regions.cpp:101:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() <= sq && g[q2].size() <= sq && m[q1][q2] == 0) {
                             ~~~~~~~~~~~~~^~~~~
regions.cpp:102:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < g[q2].size(); j ++) {
                    ~~^~~~~~~~~~~~~~
regions.cpp:106:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < g[q1].size(); j ++) {
                    ~~^~~~~~~~~~~~~~
regions.cpp:111:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < g[q2].size(); j ++) {
                    ~~^~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12664 KB Output is correct
2 Incorrect 12 ms 11000 KB Output isn't correct
3 Incorrect 13 ms 11128 KB Output isn't correct
4 Incorrect 15 ms 11128 KB Output isn't correct
5 Incorrect 21 ms 11128 KB Output isn't correct
6 Correct 24 ms 11336 KB Output is correct
7 Incorrect 46 ms 11204 KB Output isn't correct
8 Incorrect 32 ms 11296 KB Output isn't correct
9 Correct 76 ms 11704 KB Output is correct
10 Incorrect 131 ms 11924 KB Output isn't correct
11 Incorrect 184 ms 12320 KB Output isn't correct
12 Incorrect 236 ms 12792 KB Output isn't correct
13 Incorrect 321 ms 12608 KB Output isn't correct
14 Incorrect 485 ms 14820 KB Output isn't correct
15 Correct 600 ms 17276 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1861 ms 18260 KB Output isn't correct
2 Incorrect 2260 ms 17200 KB Output isn't correct
3 Incorrect 3802 ms 21984 KB Output isn't correct
4 Incorrect 578 ms 13816 KB Output isn't correct
5 Incorrect 607 ms 15324 KB Output isn't correct
6 Incorrect 1596 ms 46008 KB Output isn't correct
7 Incorrect 2357 ms 59784 KB Output isn't correct
8 Incorrect 3469 ms 107736 KB Output isn't correct
9 Incorrect 5531 ms 25444 KB Output isn't correct
10 Runtime error 2437 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Execution timed out 8060 ms 26476 KB Time limit exceeded
12 Incorrect 2909 ms 27476 KB Output isn't correct
13 Incorrect 4043 ms 28688 KB Output isn't correct
14 Incorrect 5815 ms 58916 KB Output isn't correct
15 Incorrect 7296 ms 36872 KB Output isn't correct
16 Incorrect 6870 ms 41576 KB Output isn't correct
17 Incorrect 6881 ms 70952 KB Output isn't correct