oj.uz

Submission #274445

# Submission time Handle Problem Language Result Execution time Memory
274445 2020-08-19T11:56:36 Z evpipis Regions (IOI09_regions) C++11
55 / 100
 8000 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int k = 100, len = 2e5+5;
int cnt_st[len], cnt_en[len], order[len], cnt;
vector<int> vec[len], adj[len], store_big, buck[len];
int par[len], reg[len], big[len], n, r, q;
map<int, int> prec[len];

struct node{
    int val;
    node *lef, *rig;

    node(int v = 0, node *l = NULL, node *r = NULL){
        val = v;
        lef = l;
        rig = r;
    }
};

typedef node *pnode;
pnode null, root[len];

pnode update(pnode t, int l, int r, int i){
    if (l == r)
        return new node(t->val+1, null, null);

    int mid = (l+r)/2;
    if (i <= mid)
        return new node(t->val+1, update(t->lef, l, mid, i), t->rig);
    else
        return new node(t->val+1, t->lef, update(t->rig, mid+1, r, i));
}

int query(pnode t, int l, int r, int i){
    if (l == r)
        return t->val;

    int mid = (l+r)/2;
    if (i <= mid)
        return query(t->lef, l, mid, i);
    return query(t->rig, mid+1, r, i);
}

void fix(int u){
    cnt_st[u] = ++cnt;
    order[cnt] = u;
    root[u] = update(root[par[u]], 1, r, reg[u]);

    for (auto v: adj[u])
        fix(v);

    cnt_en[u] = cnt;
}

int bs(int myr, int l, int r){
    return upper_bound(vec[myr].begin(), vec[myr].end(), r) - lower_bound(vec[myr].begin(), vec[myr].end(), l);
}

int main(){
    scanf("%d %d %d", &n, &r, &q);
    scanf("%d", &reg[1]);
    buck[reg[1]].pb(1);
    for (int i = 2; i <= n; i++){
        scanf("%d %d", &par[i], &reg[i]);
        buck[reg[i]].pb(i);
        adj[par[i]].pb(i);
    }

    for (int i = 1; i <= r; i++)
        big[i] = (buck[i].size() > k);

    /// make persistent segment tree
    null = new node();
    null->lef = null->rig = null;
    root[0] = null;
    fix(1);

    /// fix vec[]
    for (int i = 1; i <= n; i++)
        vec[reg[order[i]]].pb(i);

    /// compute prec[]
    for (int i = 1; i <= r; i++)
        if (big[i])
            store_big.pb(i);

    for (int u = 1; u <= n; u++){
        if (!big[reg[u]]) continue;

        int r1 = reg[u];
        for (auto r2: store_big)
            prec[r1][r2] += bs(r2, cnt_st[u], cnt_en[u]);
    }

    // answer queries
    while (q--){
        int r1, r2;
        scanf("%d %d", &r1, &r2);

        if (!big[r1]){
            int ans = 0;
            for (auto u: buck[r1])
                ans += bs(r2, cnt_st[u], cnt_en[u]);
            printf("%d\n", ans), fflush(stdout);
        }
        else if (!big[r2]){
            int ans = 0;
            for (auto u: buck[r2])
                ans += query(root[u], 1, r, r1);
            printf("%d\n", ans), fflush(stdout);
        }
        else{
            printf("%d\n", prec[r1][r2]), fflush(stdout);
        }
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |     scanf("%d %d %d", &n, &r, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |     scanf("%d", &reg[1]);
      |     ~~~~~^~~~~~~~~~~~~~~
regions.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |         scanf("%d %d", &par[i], &reg[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |         scanf("%d %d", &r1, &r2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 16 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 22 ms 23936 KB Output is correct
5 Correct 23 ms 23936 KB Output is correct
6 Correct 35 ms 24192 KB Output is correct
7 Correct 43 ms 24312 KB Output is correct
8 Correct 58 ms 24576 KB Output is correct
9 Correct 69 ms 25856 KB Output is correct
10 Correct 110 ms 27776 KB Output is correct
11 Correct 116 ms 29176 KB Output is correct
12 Correct 180 ms 31616 KB Output is correct
13 Correct 252 ms 32376 KB Output is correct
14 Correct 779 ms 36088 KB Output is correct
15 Correct 750 ms 41980 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2270 ms 51704 KB Output is correct
2 Correct 2027 ms 51960 KB Output is correct
3 Correct 3529 ms 59688 KB Output is correct
4 Correct 491 ms 38648 KB Output is correct
5 Correct 479 ms 42904 KB Output is correct
6 Correct 771 ms 50068 KB Output is correct
7 Correct 1538 ms 61048 KB Output is correct
8 Correct 2997 ms 81208 KB Output is correct
9 Execution timed out 8022 ms 122220 KB Time limit exceeded
10 Runtime error 331 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 297 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 325 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 315 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 311 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 298 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 273 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 282 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)