Submission #155484

#	Time	Username	Problem	Language	Result	Execution time	Memory
155484		karma	Regions (IOI09_regions)	C++14	36 / 100	3506 ms	23124 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 r[N], cur, Time = 0;
vector<int> out[C], in[C], a[N], ans[C];
int n, R, Q, p, e1, e2, res = 0;

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

void GetAns(int u) {
     if(r[u] == e1) ++cur;
     else ans[e1][r[u] - 1] += 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];
    for(int i = 2; i <= n; ++i) {
        cin >> p >> r[i];
        a[p].pb(i);
    }
    DFS(1);
    while(Q --) {
        cin >> e1 >> e2;
        if(in[e2].empty()) {cout << "0\n"; continue;}
        if(int(in[e1].size()) <= Irene) {
          res = p = 0;
          for(int v: in[e1]) {
             while(p < in[e2].size() && in[e2][p] < v) ++p;
             res -= p;
          }
          p = 0;
          for(int v: out[e1]) {
             while(p < in[e2].size() && in[e2][p] <= v) ++p;
             res += p;
          }
          cout << res << '\n';
        } else {
          if(ans[e1].empty()) {
             cur = 0; ans[e1].resize(R, 0); GetAns(1);
          }
          cout << ans[e1][e2 - 1] << '\n';
        }
        cout.flush();
    }
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
              while(p < in[e2].size() && in[e2][p] < v) ++p;
                    ~~^~~~~~~~~~~~~~~
regions.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
              while(p < in[e2].size() && in[e2][p] <= v) ++p;
                    ~~^~~~~~~~~~~~~~~
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: 11 / 15
• Subtask 2: 25 / 85