oj.uz

Submission #228813

# Submission time Handle Problem Language Result Execution time Memory
228813 2020-05-02T16:52:31 Z osaaateiasavtnl Regions (IOI09_regions) C++14
40 / 100
 1904 ms 131076 KB 
#include<bits/stdc++.h>
using namespace std;
#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

#ifdef HOME
const int N = 2007;
#else
const int N = 2e5 + 7;    
#endif

const int K = 500; //K - number of vertices in big color
const int T = N/K + 7; //T - number of big colors

int n, R, q;
int color[N], par[N];
vector <int> tree[N], pos[N], who[N];

int num[N];
int cnt[N][T];

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);
        for (int i = 0; i < T; ++i)
            cnt[u][i] += cnt[v][i];
        if (num[color[v]] != -1)
            ++cnt[u][num[color[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);

    int ptr = 0;
    for (int i = 1; i <= R; ++i) {
        if (who[i].size() > K)
            num[i] = ptr++;
        else
            num[i] = -1;
    }   

    dfs(1);

    map <ii, int> mem;

    while (q--) {
        int c1, c2;
        cin >> c1 >> c2;

        if (mem.find(mp(c1, c2)) != mem.end()) {
            cout << mem[mp(c1, c2)] << endl;
            continue;
        }   

        int ans = 0;
        if (num[c2] != -1) {
            for (int u : who[c1])
                ans += cnt[u][num[c2]];   
        }   
        else {
            vector <int> &a = pos[c2];
            for (int u : who[c1]) {
                ans += upper_bound(all(a), r[u]) - upper_bound(all(a), l[u]);
            }   
        }

        cout << ans << endl;
        mem[mp(c1, c2)] = ans;
        fflush(stdout);
    }   
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14464 KB Output is correct
2 Correct 13 ms 14464 KB Output is correct
3 Correct 14 ms 14464 KB Output is correct
4 Correct 18 ms 14592 KB Output is correct
5 Correct 21 ms 15360 KB Output is correct
6 Correct 32 ms 15992 KB Output is correct
7 Correct 42 ms 17144 KB Output is correct
8 Correct 49 ms 18040 KB Output is correct
9 Correct 71 ms 23392 KB Output is correct
10 Correct 104 ms 31352 KB Output is correct
11 Correct 136 ms 39856 KB Output is correct
12 Correct 203 ms 48508 KB Output is correct
13 Correct 253 ms 46320 KB Output is correct
14 Correct 342 ms 64464 KB Output is correct
15 Correct 354 ms 84836 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 154 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Correct 1904 ms 128692 KB Output is correct
3 Runtime error 151 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Correct 355 ms 64120 KB Output is correct
5 Correct 477 ms 79824 KB Output is correct
6 Correct 700 ms 100588 KB Output is correct
7 Correct 1010 ms 127480 KB Output is correct
8 Runtime error 177 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 225 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 236 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 294 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 256 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 262 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 282 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 271 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 269 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 262 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)