oj.uz

답안 #840567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840567 2023-08-31T13:51:32 Z mat_jur Regions (IOI09_regions) C++17
55 / 100
 8000 ms 114944 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 = (int(sqrt(n))); 
	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 0 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 4 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 9 ms 464 KB Output is correct
7 Correct 29 ms 464 KB Output is correct
8 Correct 31 ms 464 KB Output is correct
9 Correct 60 ms 1372 KB Output is correct
10 Correct 106 ms 1232 KB Output is correct
11 Correct 211 ms 1616 KB Output is correct
12 Correct 309 ms 2512 KB Output is correct
13 Correct 322 ms 2384 KB Output is correct
14 Correct 500 ms 3292 KB Output is correct
15 Correct 703 ms 9368 KB Output is correct

Subtask #2
40.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2667 ms 15700 KB Output is correct
2 Correct 2557 ms 11592 KB Output is correct
3 Execution timed out 8066 ms 16244 KB Time limit exceeded
4 Correct 735 ms 3280 KB Output is correct
5 Correct 1274 ms 6880 KB Output is correct
6 Correct 1564 ms 21612 KB Output is correct
7 Correct 2193 ms 25524 KB Output is correct
8 Correct 3447 ms 65424 KB Output is correct
9 Execution timed out 8028 ms 16392 KB Time limit exceeded
10 Execution timed out 8036 ms 114944 KB Time limit exceeded
11 Execution timed out 8021 ms 19280 KB Time limit exceeded
12 Correct 6664 ms 19580 KB Output is correct
13 Execution timed out 8096 ms 22064 KB Time limit exceeded
14 Execution timed out 8045 ms 40332 KB Time limit exceeded
15 Execution timed out 8036 ms 30304 KB Time limit exceeded
16 Execution timed out 8023 ms 45824 KB Time limit exceeded
17 Execution timed out 8045 ms 61608 KB Time limit exceeded