oj.uz

Submission #447069

# Submission time Handle Problem Language Result Execution time Memory
447069 2021-07-24T11:34:42 Z BorisBarca Regions (IOI09_regions) C++14
100 / 100
 7283 ms 37656 KB 
/*
$$$$$$$\                      $$\           $$$$$$$\
$$  __$$\                     \__|          $$  __$$\
$$ |  $$ | $$$$$$\   $$$$$$\  $$\  $$$$$$$\ $$ |  $$ | $$$$$$\   $$$$$$\   $$$$$$$\ $$$$$$\
$$$$$$$\ |$$  __$$\ $$  __$$\ $$ |$$  _____|$$$$$$$\ | \____$$\ $$  __$$\ $$  _____|\____$$\
$$  __$$\ $$ /  $$ |$$ |  \__|$$ |\$$$$$$\  $$  __$$\  $$$$$$$ |$$ |  \__|$$ /      $$$$$$$ |
$$ |  $$ |$$ |  $$ |$$ |      $$ | \____$$\ $$ |  $$ |$$  __$$ |$$ |      $$ |     $$  __$$ |
$$$$$$$  |\$$$$$$  |$$ |      $$ |$$$$$$$  |$$$$$$$  |\$$$$$$$ |$$ |      \$$$$$$$\\$$$$$$$ |
\_______/  \______/ \__|      \__|\_______/ \_______/  \_______|\__|       \_______|\_______|
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define PB push_back
#define MP make_pair
#define INS insert
#define LB lower_bound
#define UB upper_bound
#define pii pair <int,int>
#define pll pair <long long, long long>
#define X first
#define Y second
#define _ << " " <<
#define sz(x) (int)x.size()
#define all(a) (a).begin(),(a).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (a); i > (b); --i)
#define FORA(i, x) for (auto &i : x)
#define REP(i, n) FOR(i, 0, n)
#define BITS(x) __builtin_popcount(x)
#define SQ(a) (a) * (a)
#define TRACE(x) cout << #x " = " << (x) << '\n';
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define umap unordered_map

typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef vector <pii> vpi;
typedef vector <ll> vll;
typedef vector <pll> vpl;
typedef vector <double> vd;
typedef vector <ld> vld;
typedef vector<string> vs;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
//find_by_order -> kti najmanji
//order_of_key -> koliko ima manjih od x
//((float) t)/CLOCKS_PER_SEC

const int MOD = 1e9 + 7;
const double PI = acos(-1);
const int INF = 1e9 + 10;
const ll INFL = 1e18 + 10;
const int ABC = 30;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dox[] = {-1, 1, 0, 0, -1, -1, 1, 1};
const int doy[] = {0, 0, -1, 1, -1, 1, -1, 1};

inline int sum(int a, int b){
	if (a + b < 0)
		return (a + b + MOD) % MOD;
	return (a + b) % MOD;
}

inline void add(int &a, int b){
	a = sum(a, b);
}

inline int mul(ll a, ll b){
	return ((a % MOD) * ((ll)b % MOD)) % MOD;
}

inline int sub(int a, int b){
	return (a - b + MOD) % MOD;
}

inline int fast_pot(ll pot, ll n){
	ll ret = 1;
	while (n){
		if (n & 1LL)
			ret = (ret * pot) % MOD;
		pot = (pot * pot) % MOD;
		n >>= 1LL;
	}
	return ret;
}

inline int divide(int a, int b){
	return mul(a, fast_pot(b, MOD - 2));
}

ll lcm(ll a, ll b){
	return abs(a * b) / __gcd(a, b);
}

inline int ccw(pii a, pii b, pii c) {
	return a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y);
}


inline int CCW(pii A, pii B, pii C){
	double val = ccw(A, B, C);
	double eps = max(max(abs(A.X), abs(A.Y)), max(max(abs(B.X), abs(B.Y)), max(abs(C.X), abs(C.Y)))) / 1e9;
	if (val <= -eps)
		return -1;
	if (val >= eps)
		return 1;
	return 0;
}

void to_upper(string &x){
	REP(i, sz(x))
		x[i] = toupper(x[i]);
}

void to_lower(string &x){
	REP(i, sz(x))
		x[i] = tolower(x[i]);
}

string its(ll x){
	if (x == 0)
		return "0";
	string ret = "";
	while (x > 0){
		ret += (x % 10) + '0';
		x /= 10;
	}
	reverse(all(ret));
	return ret;
}

ll sti(string s){
	ll ret = 0;
	REP(i, sz(s)){
		ret *= 10;
		ret += (s[i] - '0');
	}
	return ret;
}

const int N = 2e5 + 10;
const int R = 25005;
const int LOG = 18;
const int OFF = 1 << LOG;

int n, r, q, st[N], en[N], idx, reg[N];
vi e[N], emp[R];
map <int, int> answ[R];

void dfs(int node, int dad){
	st[node] = idx++;
	en[node] = st[node];
	FORA(nxt, e[node]){
		if (nxt == dad)
			continue;
		dfs(nxt, node);
		en[node] = en[nxt];
	}
}

namespace regs{
	int cnt[R], sol[505][505];

	void dfs2(int node, int dad){
		REP(i, r)
			sol[i][reg[node]] += cnt[i];
		cnt[reg[node]]++;
		FORA(nxt, e[node]){
			if (nxt == dad)
				continue;
			dfs2(nxt, node);
		}
		cnt[reg[node]]--;
	}

	void solve(){
		dfs2(0, -1);
		while (q--){
			int a, b; cin >> a >> b;
			a--, b--;
			cout << sol[a][b] << endl;
			fflush(stdout);
		}
	}
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> r >> q;
	int h; cin >> h;
	h--;
	emp[h].PB(0);
	reg[0] = h;
	REP(i, n - 1){
		int s; cin >> s >> h;
		s--;
		h--;
		reg[i + 1] = h;
		e[s].PB(i + 1);
		emp[h].PB(i + 1);
	}

	/*if (r <= 500){
		regs::solve();
		return 0;
	}*/

	dfs(0, -1);

	REP(i, r){
		sort(all(emp[i]), [&](const int &a, const int &b){
			return st[a] < st[b];
		});
	}

	REP(i, r)
		emp[i].PB(n);
	st[n] = INF;
	en[n] = INF;

	while (q--){
		int r1, r2; cin >> r1 >> r2;
		r1--, r2--;

		if (answ[r1].count(r2)){
			cout << answ[r1][r2] << endl;
			fflush(stdout);
			continue;
		}

		int sol = 0;
		int l = 0, r = 0;
		REP(i, sz(emp[r1]) - 1){
			int node = emp[r1][i];
			while (st[emp[r2][l]] < st[node])
				l++;
			while (st[emp[r2][r]] > en[node] && r)
				r--;
			while (st[emp[r2][r]] <= en[node])
				r++;
			if (l < r)
				sol += r - l;
			//cout << node + 1 _ l _ r << '\n';
		}

		cout << sol << endl;
		answ[r1][r2] = sol;
		fflush(stdout);
	}

	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6728 KB Output is correct
2 Correct 5 ms 6728 KB Output is correct
3 Correct 6 ms 6728 KB Output is correct
4 Correct 9 ms 6728 KB Output is correct
5 Correct 12 ms 6844 KB Output is correct
6 Correct 13 ms 6944 KB Output is correct
7 Correct 32 ms 6976 KB Output is correct
8 Correct 56 ms 7008 KB Output is correct
9 Correct 50 ms 7520 KB Output is correct
10 Correct 97 ms 7604 KB Output is correct
11 Correct 119 ms 7924 KB Output is correct
12 Correct 132 ms 8580 KB Output is correct
13 Correct 186 ms 8276 KB Output is correct
14 Correct 274 ms 8676 KB Output is correct
15 Correct 288 ms 12104 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1244 ms 12572 KB Output is correct
2 Correct 1191 ms 11176 KB Output is correct
3 Correct 2005 ms 16500 KB Output is correct
4 Correct 214 ms 9364 KB Output is correct
5 Correct 415 ms 11844 KB Output is correct
6 Correct 687 ms 10892 KB Output is correct
7 Correct 978 ms 11336 KB Output is correct
8 Correct 1332 ms 19284 KB Output is correct
9 Correct 2222 ms 21528 KB Output is correct
10 Correct 3222 ms 28676 KB Output is correct
11 Correct 3460 ms 23584 KB Output is correct
12 Correct 4191 ms 20356 KB Output is correct
13 Correct 5084 ms 22256 KB Output is correct
14 Correct 6426 ms 22788 KB Output is correct
15 Correct 7283 ms 29872 KB Output is correct
16 Correct 6653 ms 37656 KB Output is correct
17 Correct 6095 ms 35708 KB Output is correct