Submission #155506

#	Time	Username	Problem	Language	Result	Execution time	Memory
155506		karma	Regions (IOI09_regions)	C++14	100 / 100	2920 ms	27384 KiB

regions

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

using namespace std;

const int N = int(2e5) + 2;
const int C = 25002;
const int Irene = 700;

int r[N], cur, Time, pos[C], rev[C], cnt[N];
vector<int> out[C], in[C], a[N];
vector< vector <int> > ans, rans;
int n, R, Q, p, e1, e2, res;

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

void GetAns(int u) {
     for(int i = 0; i < cur; ++i) ans[i][r[u] - 1] += cnt[rev[i]];
     ++cnt[r[u]];
     for(int v: a[u]) GetAns(v);
     --cnt[r[u]];
}

void GetRans(int u, int e) {
     cnt[u] = 0;
     for(int v: a[u]) {
        GetRans(v, e);
        cnt[u] += cnt[v];
     }
     rans[pos[e]][r[u] - 1] += cnt[u];
     cnt[u] += (r[u] == e);
}

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);
    for(int i = 1; i <= R; ++i) {
        if(in[i].size() > Irene) rev[pos[i] = cur] = i, ++cur;
    }
    ans.resize(cur), rans.resize(cur);
    for(int i = 0; i < cur; ++i) ans[i].resize(R, 0), rans[i].resize(R, 0);
    GetAns(1);
    for(int i = 0; i < cur; ++i) GetRans(1, rev[i]);
    while(Q --) {
        cin >> e1 >> e2;
        if(in[e2].empty()) {cout << "0\n"; cout.flush(); continue;}
        if(int(in[e1].size()) <= Irene && int(in[e2].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(in[e2].size() > Irene) cout << rans[pos[e2]][e1 - 1] << '\n';
          else cout << ans[pos[e1]][e2 - 1] << '\n';
        }
        cout.flush();
    }
}

Compilation message (stderr)

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