oj.uz

답안 #431979

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431979 2021-06-17T17:58:23 Z amunduzbaev Regions (IOI09_regions) C++14
100 / 100
 3758 ms 93504 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]); }

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;
		if(id[x]) cout<<bs[id[x]][b]<<"\n";
		else if(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";
		} cout.flush();
	}
}

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 }
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9672 KB Output is correct
2 Correct 7 ms 9672 KB Output is correct
3 Correct 9 ms 9672 KB Output is correct
4 Correct 10 ms 9672 KB Output is correct
5 Correct 12 ms 9672 KB Output is correct
6 Correct 23 ms 9800 KB Output is correct
7 Correct 38 ms 9800 KB Output is correct
8 Correct 38 ms 9800 KB Output is correct
9 Correct 31 ms 10856 KB Output is correct
10 Correct 59 ms 10168 KB Output is correct
11 Correct 126 ms 10568 KB Output is correct
12 Correct 141 ms 11592 KB Output is correct
13 Correct 170 ms 10696 KB Output is correct
14 Correct 260 ms 11396 KB Output is correct
15 Correct 196 ms 18892 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1167 ms 16676 KB Output is correct
2 Correct 1307 ms 13780 KB Output is correct
3 Correct 2293 ms 21092 KB Output is correct
4 Correct 247 ms 11568 KB Output is correct
5 Correct 368 ms 16072 KB Output is correct
6 Correct 1254 ms 13212 KB Output is correct
7 Correct 1526 ms 14132 KB Output is correct
8 Correct 1080 ms 26916 KB Output is correct
9 Correct 1783 ms 21272 KB Output is correct
10 Correct 3758 ms 34504 KB Output is correct
11 Correct 3572 ms 18892 KB Output is correct
12 Correct 1173 ms 46156 KB Output is correct
13 Correct 1764 ms 48152 KB Output is correct
14 Correct 2399 ms 54200 KB Output is correct
15 Correct 3130 ms 73152 KB Output is correct
16 Correct 3013 ms 93504 KB Output is correct
17 Correct 2600 ms 82984 KB Output is correct