oj.uz

Submission #887895

# Submission time Handle Problem Language Result Execution time Memory
887895 2023-12-15T12:42:10 Z airths Regions (IOI09_regions) C++17
31 / 100
 2387 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]][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])-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
11.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 756 KB Output isn't correct
2 Incorrect 1 ms 344 KB Output isn't 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 9 ms 600 KB Output is correct
7 Correct 13 ms 600 KB Output is correct
8 Correct 18 ms 684 KB Output is correct
9 Correct 29 ms 1368 KB Output is correct
10 Correct 47 ms 1568 KB Output is correct
11 Correct 70 ms 2056 KB Output is correct
12 Correct 82 ms 2884 KB Output is correct
13 Correct 117 ms 3352 KB Output is correct
14 Incorrect 179 ms 4060 KB Output isn't correct
15 Incorrect 210 ms 8048 KB Output isn't correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1322 ms 9976 KB Output isn't correct
2 Incorrect 1411 ms 9700 KB Output isn't correct
3 Incorrect 1744 ms 12900 KB Output isn't correct
4 Correct 156 ms 4116 KB Output is correct
5 Correct 242 ms 6432 KB Output is correct
6 Incorrect 320 ms 10436 KB Output isn't correct
7 Incorrect 622 ms 13412 KB Output isn't correct
8 Incorrect 656 ms 25112 KB Output isn't correct
9 Correct 1354 ms 18980 KB Output is correct
10 Incorrect 1823 ms 47324 KB Output isn't correct
11 Correct 2387 ms 23996 KB Output is correct
12 Incorrect 784 ms 22500 KB Output isn't correct
13 Incorrect 1065 ms 23948 KB Output isn't correct
14 Incorrect 1273 ms 28192 KB Output isn't correct
15 Incorrect 1823 ms 29924 KB Output isn't correct
16 Incorrect 1974 ms 38384 KB Output isn't correct
17 Incorrect 1881 ms 40168 KB Output isn't correct