oj.uz

답안 #117043

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
117043 2019-06-14T14:03:45 Z eriksuenderhauf Regions (IOI09_regions) C++11
0 / 100
 811 ms 30840 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 2e5 + 5;
const int MAXR = 3e4 + 5;
const int MAGIC = 400;
const double eps = 1e-9;
int par[MAXN], col[MAXN], cnt[MAXN];
vi ans[MAXR];
vi adj[MAXN], ind[MAXR], idx[MAXR];
int n, r, q, t = 0, st[MAXN], en[MAXN];
map<pii,int> dp;

void dfs(int u, int x, int d) {
	int fl = 0;
	if (col[u] == x)
		fl++;
	for (int v: adj[u])
		dfs(v, x, d + fl);
	ans[x][col[u]] += d;
}

void dfs(int u) {
	st[u] = t++;
	ind[col[u]].pb(st[u]);
	idx[col[u]].pb(u);
	for (int v: adj[u])
		dfs(v);
	en[u] = t;
}

int main() {
	scanf("%d %d %d", &n, &r, &q);
	scanf("%d", &col[0]);
	for (int i = 1; i < n; i++) {
		scanf("%d %d", &par[i], &col[i]);
		adj[--par[i]].pb(i);
		cnt[col[i]]++;
	}
	dfs(0);
	for (int i = 1; i <= r; i++)
		if (cnt[i] > MAGIC) {
			ans[i].resize(r + 2);
			dfs(0, i, 0);
		}
	while (q--) {
		int x, y;
		scanf("%d %d", &x, &y);
		if (cnt[x] <= MAGIC) {
			if (dp.count(mp(x, y))) {
				printf("%d\n", dp[mp(x, y)]);
				continue;
			}
			int anscnt = 0;
			for (int j = 0; j < idx[x].size(); j++) {
				int lo = lower_bound(ind[y].begin(), ind[y].end(), st[idx[x][j]]) - ind[y].begin();
				int hi = lower_bound(ind[y].begin(), ind[y].end(), en[idx[x][j]]) - ind[y].begin();
				anscnt += hi - lo;
			}
			printf("%d\n", anscnt);
			dp[mp(x, y)] = anscnt;
		} else {
			printf("%d\n", ans[x][y]);
		}
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:86:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < idx[x].size(); j++) {
                    ~~^~~~~~~~~~~~~~~
regions.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &r, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &col[0]);
  ~~~~~^~~~~~~~~~~~~~~
regions.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &par[i], &col[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 7 ms 7040 KB Time limit exceeded (wall clock)
2 Execution timed out 9 ms 7040 KB Time limit exceeded (wall clock)
3 Execution timed out 8 ms 7036 KB Time limit exceeded (wall clock)
4 Execution timed out 8 ms 7168 KB Time limit exceeded (wall clock)
5 Execution timed out 7 ms 7172 KB Time limit exceeded (wall clock)
6 Execution timed out 7 ms 7168 KB Time limit exceeded (wall clock)
7 Execution timed out 8 ms 7168 KB Time limit exceeded (wall clock)
8 Execution timed out 7 ms 7168 KB Time limit exceeded (wall clock)
9 Execution timed out 10 ms 7680 KB Time limit exceeded (wall clock)
10 Execution timed out 12 ms 7680 KB Time limit exceeded (wall clock)
11 Execution timed out 17 ms 7936 KB Time limit exceeded (wall clock)
12 Execution timed out 15 ms 8448 KB Time limit exceeded (wall clock)
13 Execution timed out 19 ms 8184 KB Time limit exceeded (wall clock)
14 Execution timed out 20 ms 8752 KB Time limit exceeded (wall clock)
15 Execution timed out 21 ms 10492 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 66 ms 11816 KB Time limit exceeded (wall clock)
2 Execution timed out 65 ms 10872 KB Time limit exceeded (wall clock)
3 Execution timed out 55 ms 13432 KB Time limit exceeded (wall clock)
4 Execution timed out 24 ms 8952 KB Time limit exceeded (wall clock)
5 Execution timed out 21 ms 9984 KB Time limit exceeded (wall clock)
6 Execution timed out 144 ms 11816 KB Time limit exceeded (wall clock)
7 Execution timed out 105 ms 12372 KB Time limit exceeded (wall clock)
8 Execution timed out 172 ms 19452 KB Time limit exceeded (wall clock)
9 Execution timed out 90 ms 16808 KB Time limit exceeded (wall clock)
10 Execution timed out 463 ms 30840 KB Time limit exceeded (wall clock)
11 Execution timed out 102 ms 17144 KB Time limit exceeded (wall clock)
12 Execution timed out 258 ms 18756 KB Time limit exceeded (wall clock)
13 Execution timed out 146 ms 18756 KB Time limit exceeded (wall clock)
14 Execution timed out 811 ms 20236 KB Time limit exceeded (wall clock)
15 Execution timed out 126 ms 22312 KB Time limit exceeded (wall clock)
16 Execution timed out 112 ms 25772 KB Time limit exceeded (wall clock)
17 Execution timed out 200 ms 26616 KB Time limit exceeded (wall clock)