Submission #485692

#	Time	Username	Problem	Language	Result	Execution time	Memory
485692		qwerasdfzxcl	Regions (IOI09_regions)	C++14	100 / 100	3475 ms	54396 KiB

regions

#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 (stderr)

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 / 15
• Subtask 2: 85 / 85