oj.uz

Submission #887891

# Submission time Handle Problem Language Result Execution time Memory
887891 2023-12-15T12:38:46 Z airths Regions (IOI09_regions) C++17
31 / 100
 2690 ms 47316 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 l = 0;
			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])-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;
}

Compilation message

regions.cpp: In function 'void scn()':
regions.cpp:159:7: warning: unused variable 'l' [-Wunused-variable]
  159 |    ll l = 0;
      |       ^

Subtask #1
11.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 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 11 ms 600 KB Output is correct
7 Correct 16 ms 600 KB Output is correct
8 Correct 17 ms 852 KB Output is correct
9 Correct 25 ms 1620 KB Output is correct
10 Correct 51 ms 1732 KB Output is correct
11 Correct 71 ms 2132 KB Output is correct
12 Correct 79 ms 2980 KB Output is correct
13 Correct 108 ms 3052 KB Output is correct
14 Incorrect 168 ms 4316 KB Output isn't correct
15 Incorrect 197 ms 8004 KB Output isn't correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1326 ms 9804 KB Output isn't correct
2 Incorrect 1458 ms 9716 KB Output isn't correct
3 Incorrect 1914 ms 12888 KB Output isn't correct
4 Correct 149 ms 4116 KB Output is correct
5 Correct 208 ms 6864 KB Output is correct
6 Incorrect 319 ms 10432 KB Output isn't correct
7 Incorrect 693 ms 13404 KB Output isn't correct
8 Incorrect 736 ms 25128 KB Output isn't correct
9 Correct 1522 ms 18972 KB Output is correct
10 Incorrect 1812 ms 47316 KB Output isn't correct
11 Correct 2690 ms 23992 KB Output is correct
12 Incorrect 790 ms 22500 KB Output isn't correct
13 Incorrect 1134 ms 23944 KB Output isn't correct
14 Incorrect 1383 ms 28240 KB Output isn't correct
15 Incorrect 1953 ms 29920 KB Output isn't correct
16 Incorrect 1872 ms 38392 KB Output isn't correct
17 Incorrect 1966 ms 40132 KB Output isn't correct