oj.uz

Submission #559611

# Submission time Handle Problem Language Result Execution time Memory
559611 2022-05-10T09:32:21 Z Codurr Regions (IOI09_regions) C++14
70 / 100
 8000 ms 33416 KB 
#include "bits/stdc++.h"
using namespace std;

#define int long long //Avoid if time complexity very close to limit
#define ll long long
#define sz(x) (int)((x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define f first
#define s second

void setIO(string s = "") {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s)) {
		freopen((s + ".in").c_str(), "r", stdin);
		freopen((s + ".out").c_str(), "w", stdout);
	}
}

//Imp consts
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 1;
const int MAXN1 = 3e4 + 1;
const int INF = 1e18 + 5;
const double pi = 3.14159265358979323846;
const double ep = 1e-20;

vector<int> reg[MAXN1], adj[MAXN];
vector<vector<int>> sub(MAXN1);
vector<int> R(MAXN);
int timer, en[MAXN], st[MAXN];

void dfs(int s, int e) {
	st[s] = timer++;
	reg[R[s]].push_back(timer - 1);
	for (auto u : adj[s])
		if (u != e)
			dfs(u, s);
	en[s] = timer - 1;
}

signed main() {
	setIO();
	int n, r, q;
	cin >> n >> r >> q;
	cin >> R[1];
	sub[R[1]].push_back(1);
	for (int i = 2; i <= n; i++) {
		int x;
		cin >> x >> R[i];
		sub[R[i]].push_back(i);
		adj[x].push_back(i);
		adj[i].push_back(x);
	}
	dfs(1, 0);
	while (q--) {
		int r1, r2;
		cin >> r1 >> r2;
		int ans = 0;
		for (auto u : sub[r1])
			ans += upper_bound(all(reg[r2]), en[u]) - lower_bound(all(reg[r2]), st[u]);
		cout << ans << endl;
	}
	return 0;
}

Compilation message

regions.cpp: In function 'void setIO(std::string)':
regions.cpp:15:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:16:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   freopen((s + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8016 KB Output is correct
2 Correct 4 ms 8016 KB Output is correct
3 Correct 6 ms 8016 KB Output is correct
4 Correct 8 ms 7960 KB Output is correct
5 Correct 11 ms 8016 KB Output is correct
6 Correct 20 ms 8016 KB Output is correct
7 Correct 28 ms 8144 KB Output is correct
8 Correct 35 ms 8144 KB Output is correct
9 Correct 48 ms 8708 KB Output is correct
10 Correct 81 ms 8780 KB Output is correct
11 Correct 125 ms 9120 KB Output is correct
12 Correct 142 ms 9732 KB Output is correct
13 Correct 184 ms 9956 KB Output is correct
14 Correct 289 ms 10296 KB Output is correct
15 Correct 262 ms 13392 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8087 ms 14024 KB Time limit exceeded
2 Execution timed out 8038 ms 13952 KB Time limit exceeded
3 Execution timed out 8093 ms 16336 KB Time limit exceeded
4 Correct 238 ms 10568 KB Output is correct
5 Correct 321 ms 12220 KB Output is correct
6 Correct 1254 ms 12140 KB Output is correct
7 Correct 1509 ms 13612 KB Output is correct
8 Correct 1194 ms 19328 KB Output is correct
9 Correct 1976 ms 20692 KB Output is correct
10 Correct 4152 ms 25896 KB Output is correct
11 Correct 4655 ms 23772 KB Output is correct
12 Correct 5538 ms 21356 KB Output is correct
13 Correct 5373 ms 22572 KB Output is correct
14 Execution timed out 8010 ms 23128 KB Time limit exceeded
15 Execution timed out 8077 ms 26688 KB Time limit exceeded
16 Correct 6835 ms 33416 KB Output is correct
17 Execution timed out 8013 ms 32432 KB Time limit exceeded