oj.uz

답안 #840444

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840444 2023-08-31T11:35:40 Z mat_jur Regions (IOI09_regions) C++17
60 / 100
 8000 ms 45864 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 = 2000; 
	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 3 ms 208 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 13 ms 464 KB Output is correct
7 Correct 22 ms 464 KB Output is correct
8 Correct 33 ms 464 KB Output is correct
9 Correct 49 ms 1372 KB Output is correct
10 Correct 117 ms 1232 KB Output is correct
11 Correct 157 ms 1616 KB Output is correct
12 Correct 261 ms 2512 KB Output is correct
13 Correct 440 ms 2384 KB Output is correct
14 Correct 497 ms 2896 KB Output is correct
15 Correct 666 ms 8752 KB Output is correct

Subtask #2
45.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3163 ms 9544 KB Output is correct
2 Correct 3146 ms 8348 KB Output is correct
3 Correct 7398 ms 15228 KB Output is correct
4 Correct 800 ms 3328 KB Output is correct
5 Correct 1295 ms 6892 KB Output is correct
6 Correct 2876 ms 5800 KB Output is correct
7 Correct 5818 ms 7436 KB Output is correct
8 Correct 7695 ms 17880 KB Output is correct
9 Execution timed out 8019 ms 16348 KB Time limit exceeded
10 Execution timed out 8021 ms 27324 KB Time limit exceeded
11 Execution timed out 8074 ms 19312 KB Time limit exceeded
12 Correct 6742 ms 19664 KB Output is correct
13 Execution timed out 8025 ms 22112 KB Time limit exceeded
14 Execution timed out 8050 ms 21704 KB Time limit exceeded
15 Execution timed out 8018 ms 30272 KB Time limit exceeded
16 Execution timed out 8096 ms 45864 KB Time limit exceeded
17 Execution timed out 8054 ms 43268 KB Time limit exceeded