oj.uz

답안 #1066204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1066204 2024-08-19T16:24:38 Z Nonoze Regions (IOI09_regions) C++17
18 / 100
 1436 ms 131072 KB 
/*
*	Author: Nonoze
*	Created: Monday 19/08/2024
*/
#include <bits/stdc++.h>
using namespace std;

#ifndef _IN_LOCAL
	#define dbg(...)
#endif

// #define endl '\n'
#define endlfl '\n' << flush
#define quit(x) return (void)(cout << x << endl)

template<typename T> void read(T& x) { cin >> x;}
template<typename T1, typename T2> void read(pair<T1, T2>& p) { read(p.first), read(p.second);}
template<typename T> void read(vector<T>& v) { for (auto& x : v) read(x); }
template<typename T1, typename T2> void read(T1& x, T2& y) { read(x), read(y); }
template<typename T1, typename T2, typename T3> void read(T1& x, T2& y, T3& z) { read(x), read(y), read(z); }
template<typename T1, typename T2, typename T3, typename T4> void read(T1& x, T2& y, T3& z, T4& zz) { read(x), read(y), read(z), read(zz); }
template<typename T> void print(vector<T>& v) { for (auto& x : v) cout << x << ' '; cout << endl; }

#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
#define cmax(a, b) a = max(a, b)

#define int long long
const int inf = numeric_limits<int>::max() / 4;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7, LOG=25;



void solve();

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	// cin >> tt;
	while(tt--) solve();
	return 0;
}


struct SegTree {
	int n, k;
	vector<map<int, int>> t;
	SegTree(int _n, int _k) {
		n=_n, k=_k;
		t.resize(4*n);
	}
	void build(int v, int tl, int tr, vector<int>& a) {
		if (tl==tr) {
			t[v][a[tl]]=1;
			return;
		}
		int tm=(tl+tr)/2;
		build(2*v, tl, tm, a);
		build(2*v+1, tm+1, tr, a);
		for (auto u: t[2*v]) t[v][u.fi]+=u.se;
		for (auto u: t[2*v+1]) t[v][u.fi]+=u.se;
	}
	int query(int v, int tl, int tr, int l, int r, int val) {
		if (l>r) return 0;
		if (tl==l && tr==r) return t[v][val];
		int tm=(tl+tr)/2;
		return query(2*v, tl, tm, l, min(r, tm), val)+query(2*v+1, tm+1, tr, max(l, tm+1), r, val);
	}
};

int n, k, m=0, q, SQRT;
vector<int> a, in, out, tobuild;
vector<vector<int>> adj, calc;
string s;

void dfs(int u, int i, int cnt) {
	if (a[u]==i) cnt++;
	else calc[i][a[u]]+=cnt;
	for (auto v: adj[u]) dfs(v, i, cnt);
}

void dfs(int u) {
	in[u]=m++;
	tobuild.pb(a[u]);
	for (auto v: adj[u]) dfs(v);
	out[u]=m;
}

void solve() {
	read(n, k, q); SQRT=sqrt(n);
	a.clear(), a.resize(n), adj.clear(), adj.resize(n);
	vector<int> cnt(k, 0);
	vector<vector<int>> nodes(k);
	in.clear(), in.resize(n), out.clear(), out.resize(n);
	for (int i=0; i<n; i++) {
		if (i) {
			int x; read(x); x--;
			adj[x].pb(i);
		}
		read(a[i]); a[i]--; cnt[a[i]]++;
		nodes[a[i]].pb(i);
	}
	SegTree st(n, k);
	dfs(0);
	st.build(1, 0, n-1, tobuild);
	calc.resize(k);
	for (int i=0; i<k; i++) {
		if (cnt[i]>=SQRT) {
			calc[i].resize(k);
			dfs(0, i, 0);
		}
	}
	while (q--) {
		int u, v; read(u, v); u--, v--;
		if (cnt[u]>=SQRT) {
			cout << calc[u][v] << endl;
			continue;
		}
		int ans=0;
		for (auto x: nodes[u]) {
			ans+=st.query(1, 0, n-1, in[x], out[x]-1, v);
		}
		cout << ans << endl;
	}
}

Subtask #1
13.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 8 ms 1236 KB Output is correct
6 Correct 18 ms 2320 KB Output is correct
7 Correct 41 ms 5748 KB Output is correct
8 Correct 59 ms 7248 KB Output is correct
9 Correct 144 ms 19024 KB Output is correct
10 Correct 314 ms 40272 KB Output is correct
11 Correct 1178 ms 88400 KB Output is correct
12 Correct 1436 ms 109784 KB Output is correct
13 Correct 1298 ms 122876 KB Output is correct
14 Runtime error 1140 ms 131072 KB Execution killed with signal 9
15 Runtime error 1086 ms 131072 KB Execution killed with signal 9

Subtask #2
5.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 988 ms 131072 KB Execution killed with signal 9
2 Runtime error 794 ms 131072 KB Execution killed with signal 9
3 Runtime error 680 ms 131072 KB Execution killed with signal 9
4 Runtime error 1014 ms 131072 KB Execution killed with signal 9
5 Runtime error 1256 ms 131072 KB Execution killed with signal 9
6 Correct 906 ms 83732 KB Output is correct
7 Runtime error 1069 ms 131072 KB Execution killed with signal 9
8 Runtime error 483 ms 131072 KB Execution killed with signal 9
9 Runtime error 197 ms 131072 KB Execution killed with signal 9
10 Runtime error 183 ms 131072 KB Execution killed with signal 9
11 Runtime error 189 ms 131072 KB Execution killed with signal 9
12 Runtime error 184 ms 131072 KB Execution killed with signal 9
13 Runtime error 197 ms 131072 KB Execution killed with signal 9
14 Runtime error 216 ms 131072 KB Execution killed with signal 9
15 Runtime error 176 ms 131072 KB Execution killed with signal 9
16 Runtime error 166 ms 131072 KB Execution killed with signal 9
17 Runtime error 193 ms 131072 KB Execution killed with signal 9