Submission #291842

#	Time	Username	Problem	Language	Result	Execution time	Memory
291842		evpipis	Regions (IOI09_regions)	C++11	100 / 100	3826 ms	36856 KiB

regions

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int len = 2e5+5, k = 450;
int temp_val[len], reg[len], st[len], en[len], order[len], par[len], pos[len], cnt;
int prec1[k+5][len], prec2[k+5][len];
vector<int> adj[len], tree[len];

void fix(int u){
    st[u] = ++cnt;
    order[cnt] = u;
    tree[reg[u]].pb(u);

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

    en[u] = cnt;
}

bool is_anc(int u, int v){
    return (st[u] <= st[v] && en[v] <= en[u]);
}

int brute(vector<int> &fir, vector<int> &sec){
    int ans = 0;

    vector<int> stck(1, 0);
    for (int i = 0, j = 0; i < fir.size() || j < sec.size(); ){
        int u, tp;
        if (i == fir.size())
            u = sec[j++], tp = 2;
        else if (j == sec.size())
            u = fir[i++], tp = 1;
        else if (st[fir[i]] < st[sec[j]])
            u = fir[i++], tp = 1;
        else
            u = sec[j++], tp = 2;

        while (!is_anc(stck.back(), u))
            stck.pop_back();
        temp_val[u] = temp_val[stck.back()];
        stck.pb(u);

        if (tp == 1)
            temp_val[u]++;
        else
            ans += temp_val[u];

        //printf("u = %d, temp_val = %d\n", u, temp_val[u]);
    }

    return ans;
}

int dfs(int u, int big, int many){
    if (reg[u] == big) many++;
    else prec1[pos[big]][reg[u]] += many;

    int ans = 0;
    for (auto v: adj[u])
        ans += dfs(v, big, many);
    if (reg[u] == big) ans++;
    else prec2[pos[big]][reg[u]] += ans;

    return ans;
}

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

    fix(1);
    st[0] = 0, en[0] = n;

    for (int i = 1, j = 0; i <= r; i++)
        if (tree[i].size() > k)
            pos[i] = j++, dfs(1, i, 0);

    while (q--){
        int r1, r2;
        scanf("%d %d", &r1, &r2);
        if (tree[r1].size() > k)
            printf("%d\n", prec1[pos[r1]][r2]);
        else if (tree[r2].size() > k)
            printf("%d\n", prec2[pos[r2]][r1]);
        else
            printf("%d\n", brute(tree[r1], tree[r2]));
        fflush(stdout);
    }
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int brute(std::vector<int>&, std::vector<int>&)':
regions.cpp:30:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0, j = 0; i < fir.size() || j < sec.size(); ){
      |                            ~~^~~~~~~~~~~~
regions.cpp:30:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0, j = 0; i < fir.size() || j < sec.size(); ){
      |                                              ~~^~~~~~~~~~~~
regions.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if (i == fir.size())
      |             ~~^~~~~~~~~~~~~
regions.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         else if (j == sec.size())
      |                  ~~^~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |     scanf("%d %d %d", &n, &r, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |     scanf("%d", &reg[1]);
      |     ~~~~~^~~~~~~~~~~~~~~
regions.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |         scanf("%d %d", &par[i], &reg[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |         scanf("%d %d", &r1, &r2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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