oj.uz

Submission #430904

# Submission time Handle Problem Language Result Execution time Memory
430904 2021-06-17T07:52:02 Z milleniumEeee Regions (IOI09_regions) C++17
0 / 100
 220 ms 23556 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]);
	}
}
/*
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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4 ms 7240 KB Time limit exceeded (wall clock)
2 Execution timed out 4 ms 7368 KB Time limit exceeded (wall clock)
3 Execution timed out 4 ms 7368 KB Time limit exceeded (wall clock)
4 Execution timed out 5 ms 7368 KB Time limit exceeded (wall clock)
5 Execution timed out 5 ms 7496 KB Time limit exceeded (wall clock)
6 Execution timed out 6 ms 8392 KB Time limit exceeded (wall clock)
7 Execution timed out 6 ms 8008 KB Time limit exceeded (wall clock)
8 Execution timed out 7 ms 8264 KB Time limit exceeded (wall clock)
9 Execution timed out 20 ms 9088 KB Time limit exceeded (wall clock)
10 Execution timed out 21 ms 9416 KB Time limit exceeded (wall clock)
11 Execution timed out 28 ms 9160 KB Time limit exceeded (wall clock)
12 Execution timed out 74 ms 10188 KB Time limit exceeded (wall clock)
13 Execution timed out 43 ms 9332 KB Time limit exceeded (wall clock)
14 Execution timed out 42 ms 9324 KB Time limit exceeded (wall clock)
15 Execution timed out 110 ms 12360 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 134 ms 12028 KB Time limit exceeded (wall clock)
2 Execution timed out 100 ms 10560 KB Time limit exceeded (wall clock)
3 Execution timed out 220 ms 14136 KB Time limit exceeded (wall clock)
4 Runtime error 23 ms 16672 KB Execution killed with signal 11
5 Runtime error 25 ms 17564 KB Execution killed with signal 11
6 Runtime error 29 ms 18132 KB Execution killed with signal 11
7 Runtime error 35 ms 19352 KB Execution killed with signal 11
8 Runtime error 43 ms 23556 KB Execution killed with signal 11
9 Runtime error 45 ms 21992 KB Execution killed with signal 11
10 Runtime error 47 ms 22524 KB Execution killed with signal 11
11 Runtime error 53 ms 19904 KB Execution killed with signal 11
12 Runtime error 44 ms 22436 KB Execution killed with signal 11
13 Runtime error 45 ms 21976 KB Execution killed with signal 11
14 Runtime error 44 ms 21416 KB Execution killed with signal 11
15 Runtime error 44 ms 22548 KB Execution killed with signal 11
16 Runtime error 45 ms 22628 KB Execution killed with signal 11
17 Runtime error 54 ms 22576 KB Execution killed with signal 11