oj.uz

Submission #430912

# Submission time Handle Problem Language Result Execution time Memory
430912 2021-06-17T07:56:51 Z milleniumEeee Regions (IOI09_regions) C++17
30 / 100
 1285 ms 23644 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7240 KB Output is correct
2 Correct 6 ms 7368 KB Output is correct
3 Correct 8 ms 7332 KB Output is correct
4 Correct 11 ms 7368 KB Output is correct
5 Correct 13 ms 7544 KB Output is correct
6 Correct 28 ms 8392 KB Output is correct
7 Correct 34 ms 8008 KB Output is correct
8 Correct 40 ms 8264 KB Output is correct
9 Correct 60 ms 9032 KB Output is correct
10 Correct 64 ms 9416 KB Output is correct
11 Correct 84 ms 9160 KB Output is correct
12 Correct 177 ms 10252 KB Output is correct
13 Correct 157 ms 9416 KB Output is correct
14 Correct 122 ms 9240 KB Output is correct
15 Correct 257 ms 12304 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 763 ms 11972 KB Output is correct
2 Correct 777 ms 10560 KB Output is correct
3 Correct 1285 ms 14128 KB Output is correct
4 Runtime error 24 ms 16584 KB Execution killed with signal 11
5 Runtime error 25 ms 17640 KB Execution killed with signal 11
6 Runtime error 36 ms 18116 KB Execution killed with signal 11
7 Runtime error 34 ms 19392 KB Execution killed with signal 11
8 Runtime error 45 ms 23644 KB Execution killed with signal 11
9 Runtime error 45 ms 22100 KB Execution killed with signal 11
10 Runtime error 46 ms 22524 KB Execution killed with signal 11
11 Runtime error 48 ms 19828 KB Execution killed with signal 11
12 Runtime error 59 ms 22448 KB Execution killed with signal 11
13 Runtime error 43 ms 22080 KB Execution killed with signal 11
14 Runtime error 44 ms 21436 KB Execution killed with signal 11
15 Runtime error 43 ms 22592 KB Execution killed with signal 11
16 Runtime error 44 ms 22532 KB Execution killed with signal 11
17 Runtime error 46 ms 22592 KB Execution killed with signal 11