oj.uz

Submission #887892

# Submission time Handle Problem Language Result Execution time Memory
887892 2023-12-15T12:40:55 Z airths Regions (IOI09_regions) C++17
0 / 100
 2745 ms 47336 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]][reg[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]-1)-upper_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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Incorrect 1 ms 344 KB Output isn't correct
4 Incorrect 2 ms 344 KB Output isn't correct
5 Incorrect 4 ms 344 KB Output isn't correct
6 Incorrect 7 ms 600 KB Output isn't correct
7 Incorrect 13 ms 600 KB Output isn't correct
8 Incorrect 17 ms 700 KB Output isn't correct
9 Incorrect 20 ms 1368 KB Output isn't correct
10 Incorrect 42 ms 1572 KB Output isn't correct
11 Incorrect 71 ms 2136 KB Output isn't correct
12 Incorrect 74 ms 2904 KB Output isn't correct
13 Incorrect 105 ms 3216 KB Output isn't correct
14 Incorrect 168 ms 4132 KB Output isn't correct
15 Incorrect 178 ms 8016 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1190 ms 9804 KB Output isn't correct
2 Incorrect 1449 ms 9696 KB Output isn't correct
3 Incorrect 1846 ms 12892 KB Output isn't correct
4 Incorrect 151 ms 4112 KB Output isn't correct
5 Incorrect 202 ms 6612 KB Output isn't correct
6 Incorrect 350 ms 10440 KB Output isn't correct
7 Incorrect 716 ms 13416 KB Output isn't correct
8 Incorrect 658 ms 25112 KB Output isn't correct
9 Incorrect 1460 ms 19012 KB Output isn't correct
10 Incorrect 1778 ms 47336 KB Output isn't correct
11 Incorrect 2745 ms 23984 KB Output isn't correct
12 Incorrect 799 ms 22496 KB Output isn't correct
13 Incorrect 1196 ms 23936 KB Output isn't correct
14 Incorrect 1316 ms 28188 KB Output isn't correct
15 Incorrect 1925 ms 29924 KB Output isn't correct
16 Incorrect 1853 ms 38392 KB Output isn't correct
17 Incorrect 1863 ms 40132 KB Output isn't correct