Submission #155481

#	Time	Username	Problem	Language	Result	Execution time	Memory
155481		karma	Regions (IOI09_regions)	C++14	0 / 100	129 ms	24300 KiB

regions

#include<bits/stdc++.h>
#define Task     "test"
#define pb       emplace_back

using namespace std;

const int N = int(2e5) + 7;
const int C = 25001;
const int Irene = 480;

int in[N], out[N], r[N], cur, Time = 0;
vector<int> col[C], rin[C], a[N], ans[C];
int n, R, Q, p, e1, e2, res = 0, cnt[C];

void DFS(int u) {
     in[u] = ++Time;
     rin[r[u]].pb(Time);
     for(int v: a[u]) DFS(v);
     out[u] = Time;
}

void GetAns(int u) {
     if(r[u] == e1) ++cur;
     else cnt[r[u]] += cur;
     for(int v: a[u]) GetAns(v);
     if(r[u] == e1) --cur;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> R >> Q >> r[1];
    col[r[1]].pb(1);
    for(int i = 2; i <= n; ++i) {
        cin >> p >> r[i];
        a[p].pb(i); col[r[i]].pb(i);
    }
    DFS(1);
    while(Q --) {
        cin >> e1 >> e2;
        if(col[e2].empty()) {cout << "0\n"; continue;}
        if(int(col[e1].size()) <= Irene) {
          res = 0;
          for(int v: col[e1]) {
             res +=
             upper_bound(rin[e2].begin(), rin[e2].end(), out[v]) -
             lower_bound(rin[e2].begin(), rin[e2].end(), in[v]);
          }
          cout << res << '\n';
        } else {
          if(ans[e1].empty()) {
             fill(cnt, cnt + R + 1, 0);
             cur = 0; GetAns(1);
             for(int i = 1; i <= R; ++i) ans[e1].pb(cnt[i]);
          }
          cout << ans[e1][e2 - 1] << '\n';
        }
    }
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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