oj.uz

Submission #923831

# Submission time Handle Problem Language Result Execution time Memory
923831 2024-02-07T22:38:32 Z xjonwang Regions (IOI09_regions) C++17
100 / 100
 6360 ms 33404 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ar array

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;

template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define f first
#define s second

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

template<class T> bool umin(T& a, const T& b) {
	return b<a?a=b, 1:0;
}
template<class T> bool umax(T& a, const T& b) { 
	return a<b?a=b, 1:0;
} 

ll FIRSTTRUE(function<bool(ll)> f, ll lb, ll rb) {
	while(lb<rb) {
		ll mb=(lb+rb)/2;
		f(mb)?rb=mb:lb=mb+1; 
	} 
	return lb;
}
ll LASTTRUE(function<bool(ll)> f, ll lb, ll rb) {
	while(lb<rb) {
		ll mb=(lb+rb+1)/2;
		f(mb)?lb=mb:rb=mb-1; 
	} 
	return lb;
}

template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class A, class B> void read(pair<A, B>& x);
template<class T> void read(T& x) {
	cin >> x;
}
void read(double& d) {
	string t;
	read(t);
	d=stod(t);
}
void read(long double& d) {
	string t;
	read(t);
	d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
	read(h);
	read(t...);
}
template<class A> void read(vt<A>& x) {
	EACH(a, x)
		read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
	EACH(a, x)
		read(a);
}
template<class A, class B> void read(pair<A, B>& x) {
	cin >> x.first >> x.second;
}


string to_string(char c) {
	return string(1, c);
}
string to_string(bool b) {
	return b?"true":"false";
}
string to_string(const char* s) {
	return string(s);
}
string to_string(string s) {
	return s;
}
string to_string(vt<bool> v) {
	string res;
	FOR(sz(v))
		res+=char('0'+v[i]);
	return res;
}

template<size_t S> string to_string(bitset<S> b) {
	string res;
	FOR(S)
		res+=char('0'+b[i]);
	return res;
}
template<class T> string to_string(T v) {
    bool f=1;
    string res;
    EACH(x, v) {
		if(!f)
			res+=' ';
		f=0;
		res+=to_string(x);
	}
    return res;
}
template<class A, class B> string to_string(pair<A, B>& x) {
	return to_string(x.first) + ' ' + to_string(x.second);
}

template<class A> void write(A x) {
	cout << to_string(x);
}
template<class H, class... T> void write(const H& h, const T&... t) { 
	write(h);
	write(t...);
}
void print() {
	write("\n");
}
template<class H, class... T> void print(const H& h, const T&... t) { 
	write(h);
	if(sizeof...(t))
		write(' ');
	print(t...);
}

vt<int> r;
vt<vt<int>> adj;
vt<vt<pii>> reg;
int t;

void dfs(int v) {
	int st=t++;
	EACH(u, adj[v]) dfs(u);
	reg[r[v]].pb({st, 1});
	reg[r[v]].pb({t, -1});
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, q, x, y; read(n, m, q);
	r.resize(n), reg.resize(n), adj.resize(n);
	vt<int> cnt(n, 0);
	unordered_map<int, int> lg;
	read(x); --x; cnt[x]++; r[0]=x;
	FOR(i, 1, n) {
		read(y, x); --x, --y;
		adj[y].pb(i);
		if (cnt[x]*cnt[x]<n && (cnt[x]+1)*(cnt[x]+1)>=n) lg[x]=sz(lg);
		cnt[x]++;
		r[i]=x;
	}
	dfs(0);
	FOR(n) sort(all(reg[i]));
	FOR(q) {
		read(x, y); --x, --y;
		int l=0, r=0, cnt=0, ans=0;
		while (l<sz(reg[x]) && r<sz(reg[y])) {
			if (reg[y][r].f<reg[x][l].f) {
				if (reg[y][r].s==1) ans+=cnt;
				r++;
			} else {
				cnt+=reg[x][l].s;
				l++;
			}
		}
		print(ans);
		cout.flush();
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 12 ms 600 KB Output is correct
8 Correct 12 ms 596 KB Output is correct
9 Correct 23 ms 1112 KB Output is correct
10 Correct 42 ms 1548 KB Output is correct
11 Correct 50 ms 2148 KB Output is correct
12 Correct 75 ms 2980 KB Output is correct
13 Correct 95 ms 2904 KB Output is correct
14 Correct 118 ms 3812 KB Output is correct
15 Correct 135 ms 7540 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3036 ms 9576 KB Output is correct
2 Correct 6360 ms 8332 KB Output is correct
3 Correct 3934 ms 12176 KB Output is correct
4 Correct 132 ms 3788 KB Output is correct
5 Correct 207 ms 6228 KB Output is correct
6 Correct 491 ms 6072 KB Output is correct
7 Correct 764 ms 8128 KB Output is correct
8 Correct 635 ms 15376 KB Output is correct
9 Correct 1093 ms 18288 KB Output is correct
10 Correct 1656 ms 24360 KB Output is correct
11 Correct 1701 ms 20180 KB Output is correct
12 Correct 2478 ms 20992 KB Output is correct
13 Correct 3194 ms 21348 KB Output is correct
14 Correct 4531 ms 21388 KB Output is correct
15 Correct 3060 ms 26632 KB Output is correct
16 Correct 3374 ms 33404 KB Output is correct
17 Correct 3473 ms 32404 KB Output is correct