oj.uz

Submission #228816

# Submission time Handle Problem Language Result Execution time Memory
228816 2020-05-02T16:55:19 Z osaaateiasavtnl Regions (IOI09_regions) C++14
19 / 100
 417 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 = 4e5 + 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
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28544 KB Output is correct
2 Correct 22 ms 28544 KB Output is correct
3 Correct 27 ms 28800 KB Output is correct
4 Correct 29 ms 28960 KB Output is correct
5 Correct 29 ms 30208 KB Output is correct
6 Correct 42 ms 31352 KB Output is correct
7 Correct 45 ms 33388 KB Output is correct
8 Correct 65 ms 35192 KB Output is correct
9 Correct 90 ms 45304 KB Output is correct
10 Correct 143 ms 60280 KB Output is correct
11 Correct 199 ms 77400 KB Output is correct
12 Correct 246 ms 93944 KB Output is correct
13 Correct 290 ms 83096 KB Output is correct
14 Correct 417 ms 122744 KB Output is correct
15 Runtime error 132 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
5.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 155 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 187 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 178 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Correct 407 ms 119928 KB Output is correct
5 Runtime error 123 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 160 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 173 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 175 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 235 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 281 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 299 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 274 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 272 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 287 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 282 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 279 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 272 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)