답안 #130332

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130332 2019-07-14T20:28:59 Z Markomafko972 Regions (IOI09_regions) C++14
4 / 100
3680 ms 131072 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];
stack<int> st;
 
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) {
 			int p = 0;
 			int sol = 0;
			for (int j = 0; j < g[q2].size(); j ++) {
 				while (st.size() > 0 && (d1[g[q2][j]] < d1[st.top()] || d2[st.top()] < d1[g[q2][j]])) st.pop();
 				while (p < g[q1].size() && d1[g[q1][p]] <= d1[g[q2][j]] && d1[g[q2][j]] <= d2[g[q1][p]]) {
 					st.push(g[q1][p]);
					p ++;
				}
 				
 				sol += st.size();
			}
			
			while (st.size() > 0) st.pop();
			
			cout << sol << endl;
		}
		else {
			cout << max(0, m[q1][q2]) << endl;
		}
		
	}
 
	return 0;
}

Compilation message

regions.cpp: In function 'void dfs(int)':
regions.cpp:24: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:37: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:46: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:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[i].size() > sq) {
       ~~~~~~~~~~~~^~~~
regions.cpp:74:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < g[i].size(); j ++) {
                    ~~^~~~~~~~~~~~~
regions.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() > sq && g[q2].size() > sq) {
       ~~~~~~~~~~~~~^~~~
regions.cpp:86:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() > sq && g[q2].size() > sq) {
                            ~~~~~~~~~~~~~^~~~
regions.cpp:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() <= sq && g[q2].size() <= sq) {
       ~~~~~~~~~~~~~^~~~~
regions.cpp:90:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[q1].size() <= sq && g[q2].size() <= sq) {
                             ~~~~~~~~~~~~~^~~~~
regions.cpp:93:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < g[q2].size(); j ++) {
                    ~~^~~~~~~~~~~~~~
regions.cpp:95:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      while (p < g[q1].size() && d1[g[q1][p]] <= d1[g[q2][j]] && d1[g[q2][j]] <= d2[g[q1][p]]) {
             ~~^~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12668 KB Output is correct
2 Incorrect 12 ms 11128 KB Output isn't correct
3 Incorrect 12 ms 11048 KB Output isn't correct
4 Incorrect 14 ms 11000 KB Output isn't correct
5 Incorrect 15 ms 11128 KB Output isn't correct
6 Correct 31 ms 11128 KB Output is correct
7 Incorrect 42 ms 11256 KB Output isn't correct
8 Incorrect 36 ms 11128 KB Output isn't correct
9 Correct 65 ms 11512 KB Output is correct
10 Incorrect 81 ms 11512 KB Output isn't correct
11 Incorrect 121 ms 11896 KB Output isn't correct
12 Incorrect 148 ms 12152 KB Output isn't correct
13 Incorrect 161 ms 11896 KB Output isn't correct
14 Incorrect 210 ms 14072 KB Output isn't correct
15 Correct 287 ms 16504 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1087 ms 17208 KB Output isn't correct
2 Incorrect 1216 ms 16028 KB Output isn't correct
3 Incorrect 1683 ms 18808 KB Output isn't correct
4 Incorrect 182 ms 12536 KB Output isn't correct
5 Incorrect 372 ms 13816 KB Output isn't correct
6 Incorrect 1424 ms 44980 KB Output isn't correct
7 Incorrect 2229 ms 58868 KB Output isn't correct
8 Incorrect 3283 ms 106696 KB Output isn't correct
9 Incorrect 1812 ms 18924 KB Output isn't correct
10 Runtime error 2603 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Incorrect 2801 ms 18708 KB Output isn't correct
12 Incorrect 1382 ms 24820 KB Output isn't correct
13 Incorrect 1691 ms 25016 KB Output isn't correct
14 Incorrect 3649 ms 55432 KB Output isn't correct
15 Incorrect 2802 ms 30424 KB Output isn't correct
16 Incorrect 2817 ms 35952 KB Output isn't correct
17 Incorrect 3680 ms 65712 KB Output isn't correct