oj.uz

Submission #485692

# Submission time Handle Problem Language Result Execution time Memory
485692 2021-11-09T02:21:08 Z qwerasdfzxcl Regions (IOI09_regions) C++14
100 / 100
 3475 ms 54396 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<int> adj[200200], S[25025], dfn[25025], S2[25025], dfn2[25025], P[25025];
int a[200200], in[200200], out[200200], cnt;
map<int, ll> ans[25025];

void dfs(int s){
    in[s] = ++cnt;
    S[a[s]].push_back(S[a[s]].back()+1);
    dfn[a[s]].push_back(in[s]);
    S2[a[s]].push_back(S2[a[s]].back()+1);
    dfn2[a[s]].push_back(in[s]);
    P[a[s]].push_back(s);

    for (auto &v:adj[s]) dfs(v);

    out[s] = ++cnt;
    S[a[s]].push_back(S[a[s]].back()-1);
    dfn[a[s]].push_back(out[s]);
}

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

    for (int i=1;i<=r;i++){
        S[i].push_back(0);
        dfn[i].push_back(0);
        S2[i].push_back(0);
        dfn2[i].push_back(0);
    }
    dfs(1);

    while(q--){
        int x, y;
        scanf("%d %d", &x, &y);
        if (ans[x].find(y)!=ans[x].end()) {printf("%lld\n", ans[x][y]); fflush(stdout); continue;}
        if (P[x].size()>P[y].size()){
            ll rans = 0;
            for (auto &s:P[y]){
                int idx = upper_bound(dfn[x].begin(), dfn[x].end(), in[s]) - dfn[x].begin() - 1;
                rans += S[x][idx];
            }
            ans[x][y] = rans;
            printf("%lld\n", rans);
            fflush(stdout);
        }
        else{
            ll rans = 0;
            for (auto &s:P[x]){
                int idx = lower_bound(dfn2[y].begin(), dfn2[y].end(), in[s]) - dfn2[y].begin() - 1;
                int idx2 = upper_bound(dfn2[y].begin(), dfn2[y].end(), out[s]) - dfn2[y].begin() - 1;
                rans += S2[y][idx2] - S2[y][idx];
            }
            ans[x][y] = rans;
            printf("%lld\n", rans);
            fflush(stdout);
        }
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d %d %d", &n, &r, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d", a+1);
      |     ~~~~~^~~~~~~~~~~
regions.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%d %d", &x, a+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9032 KB Output is correct
2 Correct 5 ms 9032 KB Output is correct
3 Correct 6 ms 9032 KB Output is correct
4 Correct 8 ms 9148 KB Output is correct
5 Correct 12 ms 9200 KB Output is correct
6 Correct 20 ms 9368 KB Output is correct
7 Correct 17 ms 9364 KB Output is correct
8 Correct 43 ms 9392 KB Output is correct
9 Correct 27 ms 10224 KB Output is correct
10 Correct 71 ms 10392 KB Output is correct
11 Correct 122 ms 10924 KB Output is correct
12 Correct 135 ms 11872 KB Output is correct
13 Correct 125 ms 11720 KB Output is correct
14 Correct 257 ms 12468 KB Output is correct
15 Correct 227 ms 16800 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 17820 KB Output is correct
2 Correct 1143 ms 16672 KB Output is correct
3 Correct 2037 ms 22716 KB Output is correct
4 Correct 315 ms 13556 KB Output is correct
5 Correct 204 ms 16944 KB Output is correct
6 Correct 606 ms 16164 KB Output is correct
7 Correct 870 ms 17264 KB Output is correct
8 Correct 1000 ms 27256 KB Output is correct
9 Correct 2097 ms 33580 KB Output is correct
10 Correct 3029 ms 42148 KB Output is correct
11 Correct 3475 ms 38308 KB Output is correct
12 Correct 1256 ms 31340 KB Output is correct
13 Correct 1461 ms 34156 KB Output is correct
14 Correct 2433 ms 35772 KB Output is correct
15 Correct 3113 ms 45180 KB Output is correct
16 Correct 3127 ms 54396 KB Output is correct
17 Correct 3128 ms 52012 KB Output is correct