Submission #274467

#	Time	Username	Problem	Language	Result	Execution time	Memory
274467		evpipis	Regions (IOI09_regions)	C++11	60 / 100	8053 ms	131076 KiB

regions

#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], pos[len], cnt;
vector<int> vec[len], adj[len], store_big, buck[len];
int par[len], reg[len], big[len], n, r, q;
int prec[len/k][len/k];

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){
    while (l < r){
        int mid = (l+r)/2;
        if (i <= mid)
            t = t->lef, r = mid;
        else
            t = t->rig, l = mid+1;
    }

    return t->val;
}

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])
            pos[i] = store_big.size(), 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[pos[r1]][pos[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[pos[r1]][pos[r2]]), fflush(stdout);
        }
    }
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 15 / 15
• Subtask 2: 45 / 85