oj.uz

Submission #291842

# Submission time Handle Problem Language Result Execution time Memory
291842 2020-09-05T20:51:36 Z evpipis Regions (IOI09_regions) C++11
100 / 100
 3826 ms 36856 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 9 ms 9728 KB Output is correct
4 Correct 12 ms 9728 KB Output is correct
5 Correct 12 ms 9728 KB Output is correct
6 Correct 30 ms 9984 KB Output is correct
7 Correct 31 ms 9856 KB Output is correct
8 Correct 52 ms 9856 KB Output is correct
9 Correct 59 ms 10368 KB Output is correct
10 Correct 90 ms 10400 KB Output is correct
11 Correct 138 ms 10752 KB Output is correct
12 Correct 170 ms 11136 KB Output is correct
13 Correct 173 ms 10880 KB Output is correct
14 Correct 284 ms 11520 KB Output is correct
15 Correct 304 ms 14080 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1095 ms 15344 KB Output is correct
2 Correct 1319 ms 13944 KB Output is correct
3 Correct 2190 ms 17504 KB Output is correct
4 Correct 245 ms 11512 KB Output is correct
5 Correct 430 ms 13184 KB Output is correct
6 Correct 627 ms 16968 KB Output is correct
7 Correct 1427 ms 15352 KB Output is correct
8 Correct 1108 ms 29176 KB Output is correct
9 Correct 2619 ms 19704 KB Output is correct
10 Correct 2986 ms 36856 KB Output is correct
11 Correct 3826 ms 19832 KB Output is correct
12 Correct 1318 ms 21756 KB Output is correct
13 Correct 2009 ms 22136 KB Output is correct
14 Correct 2554 ms 25336 KB Output is correct
15 Correct 2970 ms 27128 KB Output is correct
16 Correct 2981 ms 34424 KB Output is correct
17 Correct 2941 ms 36396 KB Output is correct