Submission #559611

#	Time	Username	Problem	Language	Result	Execution time	Memory
559611		Codurr	Regions (IOI09_regions)	C++14	70 / 100	8093 ms	33416 KiB

regions

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

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 / 15
• Subtask 2: 55 / 85