답안 #431983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431983 2021-06-17T18:03:11 Z amunduzbaev Regions (IOI09_regions) C++14
100 / 100
4250 ms 105508 KB
/* made by amunduzbaev */
 
#include "bits/stdc++.h"
 
using namespace std;
 
//~ #include <ext/pb_ds/assoc_container.hpp>
//~ #include <ext/pb_ds/tree_policy.hpp>
//~ using namespace __gnu_pbds;
//~ template<class T> using oset = tree<T, 
//~ null_type, less_equal<T>, rb_tree_tag, 
//~ tree_order_statistics_node_update>;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define mem(arr, v) memset(arr, v, sizeof arr)
//~ #define int long long
#define degub(x) cout<<#x<<" : "<<x<<"\n"
#define GG cout<<"here"<<endl;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T> bool umax(T& a, const T& b) { return a < b ? a = b, true : false; }
template<int sz> using tut = array<int, sz>;
void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
	freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
 
const int N = 2e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
const int B = 500;
 
#define MULTI 0
int n, m, k, t, q, ans, res, a[N];
int last[N], id[N], cnt[N];
int bs[N / B + 10][N];
int sb[N][N / B + 10];
int tin[N], tout[N];
vii edges[N];
vpii cmp[N];

//~ BIG_SMALL BIG_BIG
int cur;
void bsdfs(int u, int cur, int p = -1, int cnt = 0){
	if(id[a[u]] == cur) cnt++;
	//~ cout<<cur<<" "<<id[a[u]]<<" "<<cnt<<"\n";
	bs[cur][a[u]] += cnt;
	for(auto x : edges[u]) bsdfs(x, cur, u, cnt);
}

//~ SMALL_BIG
map<int, int> sbdfs(int u, int p = -1){
	map<int, int> cnt;
	tin[u] = t++;
	for(auto x : edges[u]) {
		map<int, int> tmp = sbdfs(x, u);
		if(sz(tmp) > sz(cnt)) swap(cnt, tmp);
		for(auto x : tmp) cnt[x.ff] += x.ss;
	}  tout[u] = t - 1;
	if(id[a[u]]) cnt[id[a[u]]]++;
	else for(auto x : cnt) sb[a[u]][x.ff] += x.ss;
	return cnt;
}

bool par(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }

map<pii, int> cach;

void solve(int t_case){
	cin>>n>>m>>q;
	cin>>a[1];
	for(int i=2;i<=n;i++){
		int p; cin>>p>>a[i];
		edges[p].pb(i);
	}
	
	for(int i=1;i<=n;i++) cnt[a[i]]++;
	int last = 1;
	for(int i=1;i<=m;i++){
		if(cnt[i] > B) id[i] = last++;
	}
	
	for(int i=1;i<last;i++) bsdfs(1, i);
	sbdfs(1);
	for(int i=1;i<=n;i++) cmp[a[i]].pb({tin[i], tout[i]});
	for(int i=1;i<=m;i++) sort(all(cmp[i]));

	for(int i=1;i<=q;i++){
		int x, b; cin>>x>>b;
		int rr;
		if(cach.count({x, b})) { cout<<cach[{x, b}]<<endl; continue; }
		if(id[x]) { rr = bs[id[x]][b]; cout<<bs[id[x]][b]<<"\n"; }
		else if(id[b]) { rr = sb[x][id[b]]; cout<<sb[x][id[b]]<<"\n"; }
		else { 
			int res = 0; 
			//~ SMALL_SMALL
			for(auto tt : cmp[x]){
				int lx = lb(all(cmp[b]), mp(tt.ff, -1)) - cmp[b].begin();
				int rx = ub(all(cmp[b]), mp(tt.ss, tt.ss)) - cmp[b].begin();
				res += rx - lx;
			} cout<<res<<"\n"; rr = res;
		} cout.flush();
		cach[{x, b}] = rr;
	}
}

signed main(){
	NeedForSpeed
	if(MULTI){
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} else solve(1);
	return 0;
}

Compilation message

regions.cpp: In function 'void usaco(std::string)':
regions.cpp:38:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 | void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:39:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9672 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 8 ms 9672 KB Output is correct
4 Correct 9 ms 9736 KB Output is correct
5 Correct 12 ms 9784 KB Output is correct
6 Correct 26 ms 10000 KB Output is correct
7 Correct 32 ms 9932 KB Output is correct
8 Correct 39 ms 10156 KB Output is correct
9 Correct 59 ms 11136 KB Output is correct
10 Correct 85 ms 10688 KB Output is correct
11 Correct 128 ms 11148 KB Output is correct
12 Correct 144 ms 12352 KB Output is correct
13 Correct 178 ms 11520 KB Output is correct
14 Correct 264 ms 12076 KB Output is correct
15 Correct 250 ms 19840 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 985 ms 18272 KB Output is correct
2 Correct 1258 ms 15524 KB Output is correct
3 Correct 2149 ms 24992 KB Output is correct
4 Correct 294 ms 13040 KB Output is correct
5 Correct 376 ms 18196 KB Output is correct
6 Correct 544 ms 15208 KB Output is correct
7 Correct 833 ms 15412 KB Output is correct
8 Correct 1289 ms 31000 KB Output is correct
9 Correct 2243 ms 29484 KB Output is correct
10 Correct 4250 ms 44532 KB Output is correct
11 Correct 4244 ms 30588 KB Output is correct
12 Correct 1423 ms 51236 KB Output is correct
13 Correct 1979 ms 55404 KB Output is correct
14 Correct 2503 ms 62868 KB Output is correct
15 Correct 3614 ms 84360 KB Output is correct
16 Correct 3202 ms 105508 KB Output is correct
17 Correct 3038 ms 94268 KB Output is correct