oj.uz

답안 #840411

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
840411 2023-08-31T10:59:41 Z mat_jur Regions (IOI09_regions) C++17
50 / 100
 8000 ms 34248 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;
//	if (r <= 500) {brut1(n, r, q); return 0;}
	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);
	}

	vector<int> start(n), end(n);
	int timer = 0;
	function<void(int, int)> dfs = [&](int v, int p) {
		start[v] = timer++;
		for(auto w : G[v]) {
			if (w == p) continue;
			dfs(w, v);
		}
		end[v] = timer-1;
	};
	dfs(0, -1);
	REP(j, q) {
		int r1, r2;
		cin >> r1 >> r2;
		r1--; r2--;
		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 ans = 0;
		for (auto v : wyst[r1]) {
			ans += a[end[v]] - get(start[v]-1);	
		}
		cout << ans << '\n';
		cout.flush();
	}

	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 6 ms 336 KB Output is correct
6 Correct 15 ms 464 KB Output is correct
7 Correct 21 ms 336 KB Output is correct
8 Correct 28 ms 464 KB Output is correct
9 Correct 46 ms 1224 KB Output is correct
10 Correct 93 ms 1120 KB Output is correct
11 Correct 157 ms 1520 KB Output is correct
12 Correct 219 ms 2276 KB Output is correct
13 Correct 302 ms 2204 KB Output is correct
14 Correct 376 ms 2676 KB Output is correct
15 Correct 562 ms 7168 KB Output is correct

Subtask #2
35.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4880 ms 7400 KB Output is correct
2 Correct 6422 ms 6676 KB Output is correct
3 Execution timed out 8054 ms 10360 KB Time limit exceeded
4 Correct 631 ms 2952 KB Output is correct
5 Correct 1018 ms 5692 KB Output is correct
6 Correct 2191 ms 5036 KB Output is correct
7 Correct 4388 ms 6504 KB Output is correct
8 Correct 6164 ms 14728 KB Output is correct
9 Execution timed out 8044 ms 14248 KB Time limit exceeded
10 Execution timed out 8045 ms 22696 KB Time limit exceeded
11 Execution timed out 8064 ms 17096 KB Time limit exceeded
12 Execution timed out 8098 ms 15540 KB Time limit exceeded
13 Execution timed out 8026 ms 17168 KB Time limit exceeded
14 Execution timed out 8054 ms 16932 KB Time limit exceeded
15 Execution timed out 8026 ms 23088 KB Time limit exceeded
16 Execution timed out 8069 ms 34248 KB Time limit exceeded
17 Execution timed out 8063 ms 31748 KB Time limit exceeded