oj.uz

Submission #446805

# Submission time Handle Problem Language Result Execution time Memory
446805 2021-07-23T10:25:50 Z BorisBarca Regions (IOI09_regions) C++14
40 / 100
 8000 ms 29568 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];

struct tournament{
	int t[2 * OFF], off;

	void init(int n){
		for (off = 1; off < n; off *= 2);
		memset(t, 0, sizeof t);
	}

	void send_prop(int node){
		for (auto c : {node * 2, node * 2 + 1})
			t[c] += t[node];
		t[node] = 0;
	}

	void update(int node, int a, int b, int lo, int hi, int  x){
		if (a > hi || b < lo)
			return;
		if (a >= lo && b <= hi){
			t[node] += x;
			return;
		}
		int mid = (a + b) / 2;
		send_prop(node);
		update(node * 2, a, mid, lo, hi, x);
		update(node * 2 + 1, mid + 1, b, lo, hi, x);
	}

	int query(int node, int a, int b, int lo, int hi){
		if (a > hi || b < lo)
			return 0;
		if (a >= lo && b <= hi)
			return t[node];
		send_prop(node);
		int mid = (a + b) / 2;
		return query(node * 2, a, mid, lo, hi) + query(node * 2 + 1, mid + 1, b, lo, hi);
	}

} T;

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;
	}

	T.init(n);
	dfs(0, -1);
	while (q--){
		int r1, r2; cin >> r1 >> r2;
		r1--, r2--;

		FORA(el, emp[r1])
			T.update(1, 0, T.off - 1, st[el], en[el], 1);
		int sol = 0;
		FORA(el, emp[r2])
			sol += T.query(1, 0, T.off - 1, st[el], st[el]);

		cout << sol << endl;
		fflush(stdout);
		FORA(el, emp[r1])
			T.update(1, 0, T.off - 1, st[el], en[el], -1);
	}

	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5576 KB Output is correct
2 Correct 4 ms 5576 KB Output is correct
3 Correct 6 ms 5576 KB Output is correct
4 Correct 5 ms 5576 KB Output is correct
5 Correct 9 ms 5704 KB Output is correct
6 Correct 22 ms 6088 KB Output is correct
7 Correct 48 ms 5960 KB Output is correct
8 Correct 40 ms 6088 KB Output is correct
9 Correct 54 ms 6728 KB Output is correct
10 Correct 83 ms 6812 KB Output is correct
11 Correct 96 ms 6788 KB Output is correct
12 Correct 156 ms 7628 KB Output is correct
13 Correct 83 ms 6856 KB Output is correct
14 Correct 86 ms 7140 KB Output is correct
15 Correct 209 ms 10172 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 906 ms 9744 KB Output is correct
2 Correct 944 ms 8392 KB Output is correct
3 Correct 1339 ms 11892 KB Output is correct
4 Correct 1299 ms 8988 KB Output is correct
5 Correct 1291 ms 11080 KB Output is correct
6 Execution timed out 8085 ms 10184 KB Time limit exceeded
7 Execution timed out 8003 ms 11200 KB Time limit exceeded
8 Execution timed out 8029 ms 16832 KB Time limit exceeded
9 Execution timed out 8061 ms 16076 KB Time limit exceeded
10 Execution timed out 8032 ms 21940 KB Time limit exceeded
11 Execution timed out 8064 ms 15228 KB Time limit exceeded
12 Execution timed out 8048 ms 17088 KB Time limit exceeded
13 Execution timed out 8058 ms 17548 KB Time limit exceeded
14 Execution timed out 8055 ms 16960 KB Time limit exceeded
15 Execution timed out 8029 ms 22208 KB Time limit exceeded
16 Execution timed out 8051 ms 29568 KB Time limit exceeded
17 Execution timed out 8050 ms 27968 KB Time limit exceeded