oj.uz

Submission #228814

# Submission time Handle Problem Language Result Execution time Memory
228814 2020-05-02T16:53:56 Z osaaateiasavtnl Regions (IOI09_regions) C++14
40 / 100
 2001 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;

        if (num[i] >= T) {
            cout << "LMAO" << endl;
            exit(0);
        }   

    }   

    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 13 ms 14464 KB Output is correct
2 Correct 14 ms 14464 KB Output is correct
3 Correct 15 ms 14464 KB Output is correct
4 Correct 18 ms 14720 KB Output is correct
5 Correct 21 ms 15360 KB Output is correct
6 Correct 30 ms 15936 KB Output is correct
7 Correct 42 ms 17136 KB Output is correct
8 Correct 48 ms 17912 KB Output is correct
9 Correct 73 ms 23416 KB Output is correct
10 Correct 115 ms 31352 KB Output is correct
11 Correct 167 ms 39852 KB Output is correct
12 Correct 200 ms 48504 KB Output is correct
13 Correct 278 ms 46200 KB Output is correct
14 Correct 366 ms 64252 KB Output is correct
15 Correct 350 ms 84608 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 2001 ms 128836 KB Output is correct
3 Runtime error 152 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Correct 365 ms 64120 KB Output is correct
5 Correct 472 ms 79876 KB Output is correct
6 Correct 728 ms 100856 KB Output is correct
7 Correct 990 ms 127632 KB Output is correct
8 Runtime error 167 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 215 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 240 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 290 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 265 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 264 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 286 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 278 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 284 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 271 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)