oj.uz

Submission #155506

# Submission time Handle Problem Language Result Execution time Memory
155506 2019-09-28T19:44:36 Z karma Regions (IOI09_regions) C++14
100 / 100
 2920 ms 27384 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6136 KB Output is correct
2 Correct 7 ms 6136 KB Output is correct
3 Correct 9 ms 6136 KB Output is correct
4 Correct 13 ms 6264 KB Output is correct
5 Correct 17 ms 6268 KB Output is correct
6 Correct 27 ms 6264 KB Output is correct
7 Correct 33 ms 6264 KB Output is correct
8 Correct 56 ms 6392 KB Output is correct
9 Correct 34 ms 6648 KB Output is correct
10 Correct 92 ms 6776 KB Output is correct
11 Correct 138 ms 6904 KB Output is correct
12 Correct 146 ms 7328 KB Output is correct
13 Correct 216 ms 7032 KB Output is correct
14 Correct 261 ms 7580 KB Output is correct
15 Correct 221 ms 9412 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1025 ms 10616 KB Output is correct
2 Correct 1255 ms 9424 KB Output is correct
3 Correct 1740 ms 12324 KB Output is correct
4 Correct 290 ms 7544 KB Output is correct
5 Correct 416 ms 8832 KB Output is correct
6 Correct 847 ms 8648 KB Output is correct
7 Correct 1128 ms 9592 KB Output is correct
8 Correct 1122 ms 13432 KB Output is correct
9 Correct 1827 ms 14304 KB Output is correct
10 Correct 2679 ms 18040 KB Output is correct
11 Correct 2920 ms 14076 KB Output is correct
12 Correct 1132 ms 16448 KB Output is correct
13 Correct 1591 ms 16636 KB Output is correct
14 Correct 2281 ms 18868 KB Output is correct
15 Correct 2456 ms 20920 KB Output is correct
16 Correct 2279 ms 26252 KB Output is correct
17 Correct 2288 ms 27384 KB Output is correct