oj.uz

답안 #431973

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431973 2021-06-17T17:51:47 Z amunduzbaev Regions (IOI09_regions) C++14
95 / 100
 3843 ms 131076 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, -1ll)) - 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 6 ms 9672 KB Output is correct
2 Correct 7 ms 9672 KB Output is correct
3 Correct 9 ms 9668 KB Output is correct
4 Correct 12 ms 9672 KB Output is correct
5 Correct 13 ms 9800 KB Output is correct
6 Correct 28 ms 9928 KB Output is correct
7 Correct 33 ms 9800 KB Output is correct
8 Correct 41 ms 9940 KB Output is correct
9 Correct 52 ms 11080 KB Output is correct
10 Correct 87 ms 10440 KB Output is correct
11 Correct 122 ms 11024 KB Output is correct
12 Correct 140 ms 12104 KB Output is correct
13 Correct 171 ms 11464 KB Output is correct
14 Correct 256 ms 12232 KB Output is correct
15 Correct 303 ms 20552 KB Output is correct

Subtask #2
80.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1094 ms 18828 KB Output is correct
2 Correct 1262 ms 16300 KB Output is correct
3 Correct 2331 ms 23932 KB Output is correct
4 Correct 277 ms 12380 KB Output is correct
5 Correct 346 ms 17288 KB Output is correct
6 Correct 1348 ms 14416 KB Output is correct
7 Correct 1654 ms 15808 KB Output is correct
8 Correct 1318 ms 30080 KB Output is correct
9 Correct 2097 ms 25440 KB Output is correct
10 Correct 3843 ms 39536 KB Output is correct
11 Correct 3593 ms 24112 KB Output is correct
12 Correct 1145 ms 71092 KB Output is correct
13 Correct 1843 ms 72656 KB Output is correct
14 Correct 2194 ms 82972 KB Output is correct
15 Correct 3118 ms 118900 KB Output is correct
16 Runtime error 146 ms 131076 KB Execution killed with signal 9
17 Correct 2713 ms 117856 KB Output is correct