oj.uz

답안 #1033300

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1033300 2024-07-24T16:13:31 Z s_tree Regions (IOI09_regions) C++17
26 / 100
 6714 ms 131072 KB 
#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 <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define vt vector
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<class T> bool chmin(T& a, const T& b) {
	return b<a?a=b, 1:0;
}
template<class T> bool chmax(T& a, const T& b) { 
	return a<b?a=b, 1:0;
} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());


const int B = 0;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int n, r, q;
	cin >> n >> r >> q;
	vt<vt<int>> g(n+1);
	vt<vt<int>> col(r+1);
	vt<int> c(n+1);
	vt<vt<ll>> precomp(r+1);
	for(int i = 1;i<=n;i++) {
		if(i>1) {
			int par;
			cin >> par;
			g[par].pb(i);
		}
		int h;
		cin >> h;
		c[i] = h;
		col[h].pb(i);
	}
	vt<int> tin(n+1);
	int timer=0;
	vt<vt<int>> tinCol(n+1);
	auto dfs = [&](int at,  auto &&dfs) -> void {
		tin[at]=++timer;	
		tinCol[c[at]].pb(tin[at]);
		for(int to:g[at]) {
			dfs(to, dfs);
		}
	};
	int fixedCol=0;
	auto dfs2 = [&](int at,  auto &&dfs2) -> int {
		int cnt=0;
		for(int to:g[at]) {
			cnt+=dfs2(to, dfs2);
		}
		precomp[fixedCol][c[at]]+=cnt;
		cnt+=(fixedCol==c[at]);
		return cnt;
	};
	dfs(1, dfs);
	for(int i = 1;i<=r;i++) {
		if(sz(col[i])>B) {
			fixedCol=i;
			precomp[i].resize(r+1);
			dfs2(1, dfs2);
		}
	}
	while(q--) {
		int r1, r2;
		cin >> r1 >> r2;
		if(sz(col[r2])>B) {
			cout << precomp[r2][r1] << endl;
		}
	}

}

Subtask #1
11.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
2 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
3 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
4 Correct 2 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Execution timed out 2 ms 916 KB Time limit exceeded (wall clock)
7 Correct 10 ms 600 KB Output is correct
8 Correct 14 ms 832 KB Output is correct
9 Correct 27 ms 1848 KB Output is correct
10 Correct 118 ms 2988 KB Output is correct
11 Correct 133 ms 2320 KB Output is correct
12 Correct 211 ms 4432 KB Output is correct
13 Correct 220 ms 3408 KB Output is correct
14 Correct 216 ms 3688 KB Output is correct
15 Correct 177 ms 6252 KB Output is correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 754 ms 8428 KB Output is correct
2 Correct 923 ms 7752 KB Output is correct
3 Correct 1056 ms 10820 KB Output is correct
4 Execution timed out 2136 ms 116340 KB Time limit exceeded (wall clock)
5 Execution timed out 1136 ms 118608 KB Time limit exceeded (wall clock)
6 Runtime error 2573 ms 131072 KB Execution killed with signal 9
7 Runtime error 2834 ms 131072 KB Execution killed with signal 9
8 Runtime error 1645 ms 131072 KB Execution killed with signal 9
9 Runtime error 3832 ms 131072 KB Execution killed with signal 9
10 Runtime error 1070 ms 131072 KB Execution killed with signal 9
11 Runtime error 2619 ms 131072 KB Execution killed with signal 9
12 Runtime error 6714 ms 131072 KB Execution killed with signal 9
13 Runtime error 4049 ms 131072 KB Execution killed with signal 9
14 Runtime error 4399 ms 131072 KB Execution killed with signal 9
15 Runtime error 1710 ms 131072 KB Execution killed with signal 9
16 Runtime error 1149 ms 131072 KB Execution killed with signal 9
17 Runtime error 1477 ms 131072 KB Execution killed with signal 9