oj.uz

Submission #155478

# Submission time Handle Problem Language Result Execution time Memory
155478 2019-09-28T18:02:48 Z karma Regions (IOI09_regions) C++14
0 / 100
 144 ms 24232 KB 
#include<bits/stdc++.h>
#define Task     "test"
#define pb       emplace_back
#define ll       long long

using namespace std;

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

int in[N], out[N], r[N], cur, Time;
vector<int> col[C], rin[C], a[N];
int n, R, Q, p, e1, e2;
ll res = 0, cnt[C];
bool vis[C];
vector<ll> ans[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, int e) {
     if(r[u] == e) ++cur;
     else cnt[r[u]] += cur;
     for(int v: a[u]) GetAns(v, e);
     if(r[u] == e) --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[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(!vis[e1]) {
             fill(cnt, cnt + R + 1, 0);
             vis[e1] = 1; cur = 0;
             GetAns(1, e1);
             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:37: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:38: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 7 ms 6776 KB Time limit exceeded (wall clock)
2 Execution timed out 7 ms 6776 KB Time limit exceeded (wall clock)
3 Execution timed out 7 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 10 ms 6904 KB Time limit exceeded (wall clock)
6 Execution timed out 9 ms 6904 KB Time limit exceeded (wall clock)
7 Execution timed out 8 ms 6780 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 12 ms 7288 KB Time limit exceeded (wall clock)
11 Execution timed out 13 ms 7764 KB Time limit exceeded (wall clock)
12 Execution timed out 15 ms 7976 KB Time limit exceeded (wall clock)
13 Execution timed out 19 ms 7800 KB Time limit exceeded (wall clock)
14 Execution timed out 20 ms 8312 KB Time limit exceeded (wall clock)
15 Execution timed out 22 ms 10236 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 42 ms 11384 KB Time limit exceeded (wall clock)
2 Execution timed out 37 ms 10232 KB Time limit exceeded (wall clock)
3 Execution timed out 43 ms 12664 KB Time limit exceeded (wall clock)
4 Execution timed out 58 ms 8440 KB Time limit exceeded (wall clock)
5 Execution timed out 22 ms 9644 KB Time limit exceeded (wall clock)
6 Execution timed out 36 ms 9660 KB Time limit exceeded (wall clock)
7 Execution timed out 43 ms 10744 KB Time limit exceeded (wall clock)
8 Execution timed out 55 ms 14584 KB Time limit exceeded (wall clock)
9 Execution timed out 106 ms 15928 KB Time limit exceeded (wall clock)
10 Execution timed out 89 ms 19716 KB Time limit exceeded (wall clock)
11 Execution timed out 105 ms 15992 KB Time limit exceeded (wall clock)
12 Execution timed out 113 ms 17304 KB Time limit exceeded (wall clock)
13 Execution timed out 103 ms 17264 KB Time limit exceeded (wall clock)
14 Execution timed out 119 ms 17328 KB Time limit exceeded (wall clock)
15 Execution timed out 144 ms 20728 KB Time limit exceeded (wall clock)
16 Execution timed out 103 ms 24232 KB Time limit exceeded (wall clock)
17 Execution timed out 102 ms 23288 KB Time limit exceeded (wall clock)