oj.uz

Submission #155481

# Submission time Handle Problem Language Result Execution time Memory
155481 2019-09-28T18:12:41 Z karma Regions (IOI09_regions) C++14
0 / 100
 129 ms 24300 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Execution timed out 9 ms 6776 KB Time limit exceeded (wall clock)
2 Execution timed out 8 ms 6820 KB Time limit exceeded (wall clock)
3 Execution timed out 8 ms 6776 KB Time limit exceeded (wall clock)
4 Execution timed out 8 ms 6776 KB Time limit exceeded (wall clock)
5 Execution timed out 13 ms 6904 KB Time limit exceeded (wall clock)
6 Execution timed out 8 ms 6776 KB Time limit exceeded (wall clock)
7 Execution timed out 8 ms 6904 KB Time limit exceeded (wall clock)
8 Execution timed out 9 ms 6904 KB Time limit exceeded (wall clock)
9 Execution timed out 9 ms 7288 KB Time limit exceeded (wall clock)
10 Execution timed out 11 ms 7336 KB Time limit exceeded (wall clock)
11 Execution timed out 15 ms 7564 KB Time limit exceeded (wall clock)
12 Execution timed out 15 ms 7976 KB Time limit exceeded (wall clock)
13 Execution timed out 16 ms 7832 KB Time limit exceeded (wall clock)
14 Execution timed out 18 ms 8312 KB Time limit exceeded (wall clock)
15 Execution timed out 26 ms 10232 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 36 ms 11176 KB Time limit exceeded (wall clock)
2 Execution timed out 39 ms 10232 KB Time limit exceeded (wall clock)
3 Execution timed out 38 ms 12664 KB Time limit exceeded (wall clock)
4 Execution timed out 21 ms 8440 KB Time limit exceeded (wall clock)
5 Execution timed out 23 ms 9720 KB Time limit exceeded (wall clock)
6 Execution timed out 33 ms 9592 KB Time limit exceeded (wall clock)
7 Execution timed out 47 ms 10616 KB Time limit exceeded (wall clock)
8 Execution timed out 51 ms 14644 KB Time limit exceeded (wall clock)
9 Execution timed out 84 ms 15992 KB Time limit exceeded (wall clock)
10 Execution timed out 103 ms 19832 KB Time limit exceeded (wall clock)
11 Execution timed out 110 ms 15932 KB Time limit exceeded (wall clock)
12 Execution timed out 115 ms 17356 KB Time limit exceeded (wall clock)
13 Execution timed out 111 ms 17284 KB Time limit exceeded (wall clock)
14 Execution timed out 129 ms 17528 KB Time limit exceeded (wall clock)
15 Execution timed out 113 ms 20776 KB Time limit exceeded (wall clock)
16 Execution timed out 106 ms 24300 KB Time limit exceeded (wall clock)
17 Execution timed out 105 ms 23300 KB Time limit exceeded (wall clock)