oj.uz

Submission #228809

# Submission time Handle Problem Language Result Execution time Memory
228809 2020-05-02T16:33:01 Z osaaateiasavtnl Regions (IOI09_regions) C++14
65 / 100
 8000 ms 58180 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 5e5 + 7;
int n, R, q;
int color[N], par[N];
vector <int> tree[N], pos[N], who[N];
int l[N], r[N], ptr = 0;
void dfs(int u) {
    l[u] = ++ptr;
    pos[color[u]].app(l[u]);
    for (int v : tree[u]) {
        dfs(v);
    }   
    r[u] = ptr;
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #endif
    cin >> n >> R >> q;
    cin >> color[1];
    for (int i = 2; i <= n; ++i) {
        cin >> par[i] >> color[i];
        tree[par[i]].app(i);
    }   
    for (int i = 1; i <= n; ++i)
        who[color[i]].app(i);
    dfs(1);
    while (q--) {
        int c1, c2;
        cin >> c1 >> c2;
        vector <int> &a = pos[c2];
        int ans = 0;
        for (int u : who[c1]) {
            ans += upper_bound(all(a), r[u]) - upper_bound(all(a), l[u]);
        }   
        cout << ans << endl;
        fflush(stdout);
    }   
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35584 KB Output is correct
2 Correct 25 ms 35584 KB Output is correct
3 Correct 26 ms 35584 KB Output is correct
4 Correct 30 ms 35584 KB Output is correct
5 Correct 32 ms 35584 KB Output is correct
6 Correct 40 ms 35712 KB Output is correct
7 Correct 55 ms 35712 KB Output is correct
8 Correct 64 ms 35744 KB Output is correct
9 Correct 77 ms 36224 KB Output is correct
10 Correct 119 ms 36480 KB Output is correct
11 Correct 158 ms 36856 KB Output is correct
12 Correct 185 ms 37496 KB Output is correct
13 Correct 235 ms 37496 KB Output is correct
14 Correct 373 ms 38144 KB Output is correct
15 Correct 326 ms 40312 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8023 ms 42232 KB Time limit exceeded
2 Execution timed out 8060 ms 41592 KB Time limit exceeded
3 Execution timed out 8019 ms 44152 KB Time limit exceeded
4 Correct 430 ms 38268 KB Output is correct
5 Correct 422 ms 39544 KB Output is correct
6 Correct 1710 ms 39928 KB Output is correct
7 Correct 2424 ms 41720 KB Output is correct
8 Correct 1841 ms 46328 KB Output is correct
9 Correct 2811 ms 49528 KB Output is correct
10 Correct 5738 ms 53240 KB Output is correct
11 Correct 6304 ms 51008 KB Output is correct
12 Correct 6981 ms 51692 KB Output is correct
13 Correct 7634 ms 51716 KB Output is correct
14 Execution timed out 8039 ms 52208 KB Time limit exceeded
15 Execution timed out 8057 ms 55260 KB Time limit exceeded
16 Execution timed out 8044 ms 58180 KB Time limit exceeded
17 Execution timed out 8039 ms 57976 KB Time limit exceeded