oj.uz

답안 #887879

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887879 2023-12-15T12:02:22 Z airths Regions (IOI09_regions) C++17
1 / 100
 7540 ms 44660 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());
		for (auto x:ed[i]){
			if (!vis[x]){
				self(self, x);
			}
		}
		rg[reg[i]].push_back(arr.size());
	};
	dfs(dfs, 1);
	vector <vector <ll>> pre;
	vector <ll> ind(r+1, -1);
	ll c = (sqrtl(n));
	fl(i,1,r+1){
		if (rg[i].size()>=c){
			ind[i]=pre.size();
			pre.push_back(vector <ll>(r+1, 0));
			fl(j,0,rg[i].size()){
				fl(k,emp[i][j], rg[i][j]){
					pre[ind[i]][arr[k]]++;
				}
			}
		}
	}
	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,rg[r1].size()){
				while (l<emp[r2].size() && emp[r2][l]<rg[r1][j]){
					if (emp[r1][j]<=emp[r2][l] && emp[r2][l]<=rg[r1][j]){
						co++;
					}
					l++;
				}
			}
			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:137:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  137 |   if (rg[i].size()>=c){
      |       ~~~~~~~~~~~~^~~
regions.cpp:27:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 | #define fl(i,a,n) for (ll i{a}; i<n; i++)
......
  140 |    fl(j,0,rg[i].size()){
      |       ~~~~~~~~~~~~~~~~            
regions.cpp:140:4: note: in expansion of macro 'fl'
  140 |    fl(j,0,rg[i].size()){
      |    ^~
regions.cpp:27:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 | #define fl(i,a,n) for (ll i{a}; i<n; i++)
......
  157 |    fl(j,0,rg[r1].size()){
      |       ~~~~~~~~~~~~~~~~~           
regions.cpp:157:4: note: in expansion of macro 'fl'
  157 |    fl(j,0,rg[r1].size()){
      |    ^~
regions.cpp:158:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     while (l<emp[r2].size() && emp[r2][l]<rg[r1][j]){
      |            ~^~~~~~~~~~~~~~~

Subtask #1
1.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is 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 8 ms 596 KB Output isn't correct
7 Incorrect 11 ms 600 KB Output isn't correct
8 Incorrect 15 ms 696 KB Output isn't correct
9 Incorrect 19 ms 1112 KB Output isn't correct
10 Incorrect 37 ms 1588 KB Output isn't correct
11 Incorrect 57 ms 2020 KB Output isn't correct
12 Incorrect 62 ms 2816 KB Output isn't correct
13 Incorrect 80 ms 3028 KB Output isn't correct
14 Incorrect 88 ms 3800 KB Output isn't correct
15 Incorrect 97 ms 7120 KB Output isn't correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 882 ms 8960 KB Output isn't correct
2 Incorrect 719 ms 9080 KB Output isn't correct
3 Incorrect 1702 ms 11628 KB Output isn't correct
4 Incorrect 126 ms 4136 KB Output isn't correct
5 Incorrect 171 ms 6260 KB Output isn't correct
6 Incorrect 430 ms 9940 KB Output isn't correct
7 Incorrect 571 ms 12812 KB Output isn't correct
8 Incorrect 2444 ms 23268 KB Output isn't correct
9 Incorrect 811 ms 18772 KB Output isn't correct
10 Incorrect 3519 ms 44660 KB Output isn't correct
11 Incorrect 1451 ms 24148 KB Output isn't correct
12 Incorrect 877 ms 20968 KB Output isn't correct
13 Incorrect 1349 ms 22164 KB Output isn't correct
14 Incorrect 1711 ms 26456 KB Output isn't correct
15 Incorrect 3126 ms 27360 KB Output isn't correct
16 Incorrect 5570 ms 33904 KB Output isn't correct
17 Incorrect 7540 ms 35900 KB Output isn't correct