답안 #291843

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
291843 2020-09-05T20:54:05 Z evpipis Regions (IOI09_regions) C++11
100 / 100
3742 ms 45816 KB
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int len = 2e5+5, len_reg = 25005, len_k = 455;
int temp_val[len], reg[len], st[len], en[len], order[len], par[len], pos[len], cnt;
int prec1[len_k][len_reg], prec2[len_k][len_reg];
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;

    int k = sqrt(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:84:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |         if (tree[i].size() > k)
      |             ~~~~~~~~~~~~~~~^~~
regions.cpp:90:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |         if (tree[r1].size() > k)
      |             ~~~~~~~~~~~~~~~~^~~
regions.cpp:92:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |         else if (tree[r2].size() > k)
      |                  ~~~~~~~~~~~~~~~~^~~
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:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |         scanf("%d %d", &r1, &r2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 7 ms 9728 KB Output is correct
3 Correct 8 ms 9728 KB Output is correct
4 Correct 11 ms 9728 KB Output is correct
5 Correct 17 ms 9728 KB Output is correct
6 Correct 27 ms 9856 KB Output is correct
7 Correct 40 ms 9856 KB Output is correct
8 Correct 41 ms 9856 KB Output is correct
9 Correct 48 ms 10240 KB Output is correct
10 Correct 112 ms 10368 KB Output is correct
11 Correct 156 ms 10752 KB Output is correct
12 Correct 187 ms 11136 KB Output is correct
13 Correct 173 ms 10880 KB Output is correct
14 Correct 253 ms 11640 KB Output is correct
15 Correct 246 ms 14780 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1076 ms 15372 KB Output is correct
2 Correct 1265 ms 13816 KB Output is correct
3 Correct 2445 ms 17400 KB Output is correct
4 Correct 350 ms 11512 KB Output is correct
5 Correct 410 ms 13184 KB Output is correct
6 Correct 662 ms 16728 KB Output is correct
7 Correct 1082 ms 18424 KB Output is correct
8 Correct 1126 ms 28920 KB Output is correct
9 Correct 2455 ms 19704 KB Output is correct
10 Correct 2476 ms 45816 KB Output is correct
11 Correct 3742 ms 19832 KB Output is correct
12 Correct 1404 ms 21752 KB Output is correct
13 Correct 1986 ms 22136 KB Output is correct
14 Correct 2412 ms 25344 KB Output is correct
15 Correct 3262 ms 27156 KB Output is correct
16 Correct 3425 ms 34428 KB Output is correct
17 Correct 3278 ms 36344 KB Output is correct