oj.uz

답안 #840457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840457 2023-08-31T11:42:39 Z mat_jur Regions (IOI09_regions) C++17
45 / 100
 8000 ms 59532 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define ROF(i,r,l) for(int i=(r);i>=(l);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
#define eb emplace_back

void brut1(int n, int r, int q) {
	vector<int> h(n);
	cin >> h[0];
	h[0]--;
	vector G(n, vector(0, 0));
	FOR(i, 1, n-1) {
		int p;
		cin >> p >> h[i];
		p--;
		h[i]--;
		G[p].eb(i);
		G[i].eb(p);
	}
	auto merge = [&](vector<int> &a, vector<int> &b) {
		REP(i, r) a[i] += b[i];
		return;
	};
	vector ans(r, vector(r, 0ll));
	function<vector<int>(int, int)> dfs = [&](int v, int p) {
		vector<int> cnt(r);
		for(auto w : G[v]) {
			if (w == p) continue;
			vector<int> b = dfs(w, v);
			merge(cnt, b);
		}
		REP(i, r) ans[h[v]][i] += cnt[i];
		cnt[h[v]]++;
		return cnt;
	};
	dfs(0, -1);
	REP(i, q) {
		int r1, r2;
		cin >> r1 >> r2;
		r1--; r2--;
		cout << ans[r1][r2] << '\n';
		cout.flush();
	}
};

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, r, q;
	cin >> n >> r >> q;
	vector<int> h(n);
	vector G(n, vector(0, 0)), wyst(r, vector(0, 0));
	cin >> h[0];
	h[0]--;
	wyst[h[0]].eb(0);
	FOR(i, 1, n-1) {
		int p;
		cin >> p >> h[i];
		p--;
		h[i]--;
		wyst[h[i]].eb(i);
		G[p].eb(i);
		G[i].eb(p);
	}
	const int B = 15*(int(sqrt(r))); 
	vector<int> big, bigIdx(n, -1);
	REP(i, r) {
		if (ssize(wyst[i]) > B) {big.eb(i); bigIdx[i] = ssize(big)-1;}
	}
	auto merge = [&](vector<int> &a, vector<int> &b) {
		REP(i, ssize(big)) a[i] += b[i];
		return;
	};
	vector ans(r, vector(ssize(big), 0ll));
	function<vector<int>(int, int)> dfs = [&](int v, int p) {
		vector<int> cnt(ssize(big));
		for(auto w : G[v]) {
			if (w == p) continue;
			vector<int> b = dfs(w, v);
			merge(cnt, b);
		}
		REP(i, ssize(big)) ans[h[v]][i] += cnt[i];
		if(bigIdx[h[v]] >= 0) cnt[bigIdx[h[v]]]++;
		return cnt;
	};
	dfs(0, -1);

	vector<int> start(n), end(n), s(n);
	int timer = 0;
	function<void(int, int)> dfs2 = [&](int v, int p) {
		start[v] = timer++;
		s[v] = 1;
		for(auto w : G[v]) {
			if (w == p) continue;
			dfs2(w, v);
			s[v] += s[w];
		}
		end[v] = timer-1;
	};
	dfs2(0, -1);
	vector pref(ssize(big), vector(n, 0));
	REP(i, ssize(big)) {
		for (auto w : wyst[big[i]]) {
			pref[i][start[w]]++;
			if(end[w]+1 < n) pref[i][end[w]+1]--;
		}
		auto get = [&](int idx) {
			if (idx < 0) return 0;
			return pref[i][idx];
		};
		REP(j, n) pref[i][j] += get(j-1);
	};

	REP(j, q) {
		int r1, r2;
		cin >> r1 >> r2;
		r1--; r2--;
		if (bigIdx[r2] >= 0) {
//			cerr << "CASE 1 \n";
			cout << ans[r1][bigIdx[r2]] << '\n';
			cout.flush();
			continue;
		}
		if (bigIdx[r1] == -1 && bigIdx[r2] == -1) {
//			cerr << "CASE 2 \n";
			vector<int> a(n, 0);
			for (auto v : wyst[r2]) {
				a[start[v]]++;
			}
			auto get = [&](int idx) {
				if (idx < 0) return 0;
				return a[idx];
			};
			REP(i, n) a[i] += get(i-1);
			ll res = 0;
			for (auto v : wyst[r1]) {
				res += a[end[v]] - get(start[v]-1);	
			}
			cout << res << '\n';
			cout.flush();
			continue;
		}
		if (bigIdx[r1] >= 0 && bigIdx[r2] == -1) {
//			cerr << "CASE 3 \n";
			ll res = 0;
			for (auto v : wyst[r2]) {
				res += pref[bigIdx[r1]][start[v]];	
			}
			cout << res << '\n';
			cout.flush();
			continue;
		}
	}

	return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 3 ms 208 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 17 ms 464 KB Output is correct
7 Correct 24 ms 496 KB Output is correct
8 Correct 34 ms 464 KB Output is correct
9 Correct 57 ms 1360 KB Output is correct
10 Correct 172 ms 1232 KB Output is correct
11 Correct 250 ms 1616 KB Output is correct
12 Correct 459 ms 2512 KB Output is correct
13 Correct 530 ms 2384 KB Output is correct
14 Correct 560 ms 2888 KB Output is correct
15 Correct 931 ms 8744 KB Output is correct

Subtask #2
30.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1801 ms 30568 KB Output is correct
2 Correct 701 ms 59532 KB Output is correct
3 Execution timed out 8045 ms 16280 KB Time limit exceeded
4 Correct 1113 ms 3280 KB Output is correct
5 Correct 1658 ms 6876 KB Output is correct
6 Correct 3736 ms 5776 KB Output is correct
7 Correct 7206 ms 7440 KB Output is correct
8 Execution timed out 8032 ms 17884 KB Time limit exceeded
9 Execution timed out 8061 ms 16316 KB Time limit exceeded
10 Execution timed out 8058 ms 27380 KB Time limit exceeded
11 Execution timed out 8005 ms 19364 KB Time limit exceeded
12 Execution timed out 8095 ms 19620 KB Time limit exceeded
13 Execution timed out 8042 ms 22140 KB Time limit exceeded
14 Execution timed out 8026 ms 21728 KB Time limit exceeded
15 Execution timed out 8023 ms 30292 KB Time limit exceeded
16 Execution timed out 8041 ms 45928 KB Time limit exceeded
17 Execution timed out 8058 ms 43208 KB Time limit exceeded