Submission #430912

#	Time	Username	Problem	Language	Result	Execution time	Memory
430912		milleniumEeee	Regions (IOI09_regions)	C++17	30 / 100	1285 ms	23644 KiB

regions

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define ll long long
template<class T>void chmax(T &a, T b){if (a < b)a = b;}
template<class T>void chmin(T &a, T b){if (b < a)a = b;}

using namespace std;

const int MAXN = (int)1e5 + 5;

int n, r, q;
int root;

vector <int> g[MAXN];

int pr[MAXN];
int reg[MAXN];

set <pii> st[MAXN];
ll ans[505][505];

void ins(set <pii> &st, int color, int cnt) {
	auto it = st.lower_bound({color, -1e9});
	int cur_cnt = cnt;
	if (it != st.end() && it->fr == color) {
		cur_cnt += it->sc;
		st.erase(it);
	}
	st.insert({color, cur_cnt});
}

void relax(set <pii> &a, set <pii> &b) {
	if (szof(a) < szof(b)) {
		swap(a, b);
	}
	for (auto [col, cnt] : b) {
		ins(a, col, cnt);
	}
}

void calc(int v) {
	for (int to : g[v]) {
		if (to != pr[v]) {
			calc(to);
			relax(st[v], st[to]);
			st[to].clear();
		}
	}
	for (auto [col, cnt] : st[v]) {
		ans[reg[v]][col] += cnt;
	}
	ins(st[v], reg[v], 1);
}

signed main() {
	scanf("%d %d %d", &n, &r, &q);
	scanf("%d", &reg[1]);
	pr[1] = -1;
	for (int i = 2; i <= n; i++) {
		scanf("%d %d", &pr[i], &reg[i]);
		g[pr[i]].pb(i);
	}
	calc(1);
	for (int i = 1, from, to; i <= q; i++) {
		scanf("%d %d", &from, &to);
		printf("%lld\n", ans[from][to]);
		fflush(stdout);
	}
}
/*
6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1
*/

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d %d %d", &n, &r, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d", &reg[1]);
      |  ~~~~~^~~~~~~~~~~~~~~
regions.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d %d", &pr[i], &reg[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%d %d", &from, &to);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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