oj.uz

Submission #887902

# Submission time Handle Problem Language Result Execution time Memory
887902 2023-12-15T12:49:40 Z airths Regions (IOI09_regions) C++17
100 / 100
 2410 ms 47324 KB 
/*
 * 
 * 	^v^
 * 
 */
#include <iostream>
#include <numeric>
#include <set>
#include <iomanip>
#include <chrono>
#include <queue>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <bitset>
#include <algorithm>
#include <array>
#include <random>

using namespace std;

using ll = long long int;
using ld = long double;

#define iamtefu ios_base::sync_with_stdio(false); cin.tie(0);
#define fl(i,a,n) for (ll i{a}; i<n; i++)
#define rfl(i,a,n) for (ll i{n-1}; i>=a; i--)
#define ty int _; for(cin>>_; _--;)
#define print(a) for(auto ele:a){cout<<ele<<" ";}cout<<'\n';
#define all(x) x.begin(), x.end()

template <typename L, typename R>
inline bool chmax(L &a, R b){if (a<b){a=b;return 1;}return 0;}
template <typename L, typename R>
inline bool chmin(L &a, R b){if (a>b){a=b;return 1;}return 0;}

template <typename L, typename R>
ostream& operator<<(ostream &fout, const pair<L, R> &p){
	fout<<"{"<<p.first<<","<<p.second<<"}";
	return fout;
}

template <typename T>
ostream& operator<<(ostream &fout, const vector <T> &v){
	for (auto &x:v){
		fout<<x<<" ";
	}
	fout<<"\n";
	return fout;
}

template <typename T>
ostream& operator<<(ostream &fout, const set <T> &st){
	for (auto &x:st){
		fout<<x<<" ";
	}
	fout<<"\n";
	return fout;
}

template <typename T>
ostream& operator<<(ostream &fout, const multiset <T> &st){
	for (auto &x:st){
		fout<<x<<" ";
	}
	fout<<"\n";
	return fout;
}

template <typename K, typename V>
ostream& operator<<(ostream &fout, const map<K, V> &mp){
	fout<<"[";
	for (auto &[x,y]:mp){
		fout<<x<<":"<<y<<" ";
	}
	fout<<"]\n";
	return fout;
}

ll gcd(ll a, ll b){
	if (b==0){
		return a;
	}
	return gcd(b, a%b);
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

ll pw(ll a, ll b, ll m){
	ll res=1;
	a%=m;
	while (b){
		if (b&1){
			res=(res*a)%m;
		}
		a=(a*a)%m;
		b/=2;
	}
	return res;
}

void scn(){
	ll n, r, q; cin>>n>>r>>q;
	vector <vector <ll>> ed(n+1);
	vector <ll> reg(n+1);
	fl(i,0,n){
		ll x;
		if (i==0){
			cin>>x;
			reg[i+1]=x;
		} else {
			ll u; cin>>x>>u;
			reg[i+1]=u;
			ed[x].push_back(i+1);
			ed[i+1].push_back(x);
		}
	}
	vector <ll> vis(n+1), arr;
	vector <vector <ll>> rg(r+1), emp(r+1);
	auto dfs=[&](const auto &self, ll i)->void{
		vis[i]++;
		arr.push_back(reg[i]);
		emp[reg[i]].push_back(arr.size());
		rg[reg[i]].push_back(0);
		ll ino = rg[reg[i]].size()-1;
		for (auto x:ed[i]){
			if (!vis[x]){
				self(self, x);
			}
		}
		rg[reg[i]][ino]=(arr.size());
	};
	dfs(dfs, 1);
	vector <vector <ll>> pre;
	vector <ll> ind(r+1, -1);
	ll c = ((ll)sqrtl(n));
	fl(i,1,r+1){
		if ((ll)rg[i].size()>=c){
			ind[i]=pre.size();
			pre.push_back(vector <ll>(r+1, 0));
			vector <ll> art(n+2, 0);
			fl(j,0,(ll)rg[i].size()){
				art[emp[i][j]]++;
				art[rg[i][j]+1]--;
			}
			fl(j,1,n+2){
				art[j]+=art[j-1];
				pre[ind[i]][arr[j-1]]+=art[j];
			}
		}
	}
	fl(i,0,q){
		ll r1, r2; cin>>r1>>r2;
		if (ind[r1]!=-1){
			cout<<pre[ind[r1]][r2]<<'\n';
			cout.flush();
		} else {
			ll co = 0;
			// cout<<"Here\n";
			// cout<<rg[r1]<<rg[r2]<<emp[r1]<<emp[r2];
			fl(j,0,(ll)rg[r1].size()){
				co+=(upper_bound(emp[r2].begin(), emp[r2].end(), rg[r1][j])-lower_bound(emp[r2].begin(), emp[r2].end(), emp[r1][j]));
			}
			cout<<co<<'\n';
			cout.flush();
		}
	}

	// not necessarily distinct
	// right down
}

int main(){
	iamtefu;
#if defined(airths)
	auto t1=chrono::high_resolution_clock::now();
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	// ty
	{
		scn();
	}
#if defined(airths)
	auto t2=chrono::high_resolution_clock::now();
	ld ti=chrono::duration_cast<chrono::nanoseconds>(t2-t1).count();
	ti*=1e-6;
	cerr<<"Time: "<<setprecision(12)<<ti;
	cerr<<"ms\n";
#endif
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 8 ms 600 KB Output is correct
7 Correct 15 ms 600 KB Output is correct
8 Correct 16 ms 708 KB Output is correct
9 Correct 26 ms 1368 KB Output is correct
10 Correct 37 ms 1576 KB Output is correct
11 Correct 60 ms 2060 KB Output is correct
12 Correct 72 ms 3204 KB Output is correct
13 Correct 99 ms 3212 KB Output is correct
14 Correct 148 ms 4052 KB Output is correct
15 Correct 189 ms 8104 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1146 ms 9808 KB Output is correct
2 Correct 1366 ms 9700 KB Output is correct
3 Correct 1769 ms 12892 KB Output is correct
4 Correct 152 ms 4116 KB Output is correct
5 Correct 211 ms 6416 KB Output is correct
6 Correct 316 ms 10432 KB Output is correct
7 Correct 659 ms 13408 KB Output is correct
8 Correct 632 ms 25120 KB Output is correct
9 Correct 1355 ms 18972 KB Output is correct
10 Correct 1741 ms 47324 KB Output is correct
11 Correct 2410 ms 23992 KB Output is correct
12 Correct 742 ms 22496 KB Output is correct
13 Correct 1085 ms 23952 KB Output is correct
14 Correct 1228 ms 28196 KB Output is correct
15 Correct 1878 ms 29928 KB Output is correct
16 Correct 1959 ms 38388 KB Output is correct
17 Correct 1861 ms 40136 KB Output is correct