# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
53617 | 2018-06-30T14:02:24 Z | baactree | Regions (IOI09_regions) | C++17 | 8000 ms | 94376 KB |
#include <bits/stdc++.h> using namespace std; int n, r, q; vector<int> adj[200005]; int arr[200005]; const int sz = 505; int dp[sz][25005]; pair<int,int> cnt[25005]; int inv[25005]; bitset<sz> bs[200005]; int le[200005], ri[200005]; vector<int> idx[25005]; vector<pair<int, int> > vec[25005]; int vn; void dfs(int now, int par) { if (inv[arr[now]] < sz)bs[now][inv[arr[now]]] = 1; bs[now] |= bs[par]; idx[arr[now]].push_back(vn); le[now] = vn++; for (auto &there : adj[now]) { if (there == par)continue; dfs(there, now); } ri[now] = vn++; if (inv[arr[now]] >= sz) vec[arr[now]].emplace_back(le[now], ri[now]); } int main() { scanf("%d%d%d", &n, &r, &q); scanf("%d", &arr[1]); cnt[arr[1]].first++; for (int i = 2; i <= n; i++) { int a, b; scanf("%d%d", &a, &b); adj[a].push_back(i); adj[i].push_back(a); arr[i] = b; cnt[arr[i]].first++; } for (int i = 0; i < 25005; i++) cnt[i].second = i; sort(cnt, cnt + 25005); reverse(cnt,cnt + 25005); for (int i = 0; i < 25005; i++) inv[cnt[i].second] = i; dfs(1, 0); for (int i = 1; i <= n; i++) { for (int j = 0; j < sz; j++) if (bs[i][j])dp[j][arr[i]]++; } for (int i = 0; i < 25005; i++) sort(vec[i].begin(), vec[i].end()); while (q--) { int a, b; scanf("%d%d", &a, &b); if (inv[a] < sz) { printf("%d\n", dp[inv[a]][b]); fflush(stdout); } else { while (true); int pre = -1; int ans = 0; for (auto x : vec[a]) { int le = x.first; int ri = x.second; if (le <= pre)continue; ans += upper_bound(idx[b].begin(), idx[b].end(), ri) - lower_bound(idx[b].begin(), idx[b].end(), le); pre = ri; } printf("%d\n", ans); fflush(stdout); } } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 8087 ms | 6520 KB | Time limit exceeded |
2 | Execution timed out | 8087 ms | 6520 KB | Time limit exceeded |
3 | Execution timed out | 8096 ms | 6520 KB | Time limit exceeded |
4 | Incorrect | 16 ms | 6768 KB | Unexpected end of file - int32 expected |
5 | Incorrect | 13 ms | 6820 KB | Unexpected end of file - int32 expected |
6 | Execution timed out | 8074 ms | 8152 KB | Time limit exceeded |
7 | Incorrect | 41 ms | 8152 KB | Unexpected end of file - int32 expected |
8 | Incorrect | 43 ms | 8152 KB | Unexpected end of file - int32 expected |
9 | Incorrect | 49 ms | 9396 KB | Unexpected end of file - int32 expected |
10 | Incorrect | 97 ms | 10480 KB | Unexpected end of file - int32 expected |
11 | Incorrect | 176 ms | 10480 KB | Unexpected end of file - int32 expected |
12 | Incorrect | 150 ms | 12092 KB | Unexpected end of file - int32 expected |
13 | Incorrect | 188 ms | 12092 KB | Unexpected end of file - int32 expected |
14 | Incorrect | 129 ms | 12092 KB | Unexpected end of file - int32 expected |
15 | Incorrect | 283 ms | 15676 KB | Unexpected end of file - int32 expected |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 892 ms | 17212 KB | Unexpected end of file - int32 expected |
2 | Incorrect | 857 ms | 17212 KB | Unexpected end of file - int32 expected |
3 | Incorrect | 1265 ms | 20796 KB | Unexpected end of file - int32 expected |
4 | Execution timed out | 8069 ms | 20796 KB | Time limit exceeded |
5 | Execution timed out | 8013 ms | 25036 KB | Time limit exceeded |
6 | Execution timed out | 8084 ms | 29416 KB | Time limit exceeded |
7 | Execution timed out | 8080 ms | 37488 KB | Time limit exceeded |
8 | Execution timed out | 8068 ms | 45856 KB | Time limit exceeded |
9 | Execution timed out | 8080 ms | 58060 KB | Time limit exceeded |
10 | Execution timed out | 8077 ms | 83532 KB | Time limit exceeded |
11 | Execution timed out | 8063 ms | 83532 KB | Time limit exceeded |
12 | Execution timed out | 8085 ms | 83532 KB | Time limit exceeded |
13 | Execution timed out | 8064 ms | 83532 KB | Time limit exceeded |
14 | Execution timed out | 8016 ms | 83532 KB | Time limit exceeded |
15 | Execution timed out | 8055 ms | 85236 KB | Time limit exceeded |
16 | Execution timed out | 8071 ms | 94376 KB | Time limit exceeded |
17 | Execution timed out | 8032 ms | 94376 KB | Time limit exceeded |