Submission #130332

#	Time	Username	Problem	Language	Result	Execution time	Memory
130332		Markomafko972	Regions (IOI09_regions)	C++14	4 / 100	3680 ms	131072 KiB

regions

#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 (stderr)

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]]) {
             ~~^~~~~~~~~~~~~~

• Subtask 1: 4 / 15
• Subtask 2: 0 / 85