oj.uz

Submission #155487

# Submission time Handle Problem Language Result Execution time Memory
155487 2019-09-28T18:35:46 Z karma Regions (IOI09_regions) C++14
36 / 100
 3640 ms 22600 KB 
#include<bits/stdc++.h>
#define Task     "test"
#define pb       emplace_back

using namespace std;

const int N = int(2e5) + 1;
const int C = 25001;
const int Irene = 480;

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

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[cnt][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);
    for(int i = 1; i <= R; ++i) {
        if(in[i].size() > Irene) ++cnt;
        pos[i] = -1;
    }
    ans.resize(cnt); cnt = 0;
    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(pos[e1] < 0) {
             pos[e1] = cnt;
             cur = 0; ans[cnt].resize(R, 0); GetAns(1);
             ++cnt;
          }
          cout << ans[pos[e1]][e2 - 1] << '\n';
        }
        cout.flush();
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:54:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
              while(p < in[e2].size() && in[e2][p] < v) ++p;
                    ~~^~~~~~~~~~~~~~~
regions.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
              while(p < in[e2].size() && in[e2][p] <= v) ++p;
                    ~~^~~~~~~~~~~~~~~
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".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:35: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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7 ms 6264 KB Time limit exceeded (wall clock)
2 Execution timed out 7 ms 6140 KB Time limit exceeded (wall clock)
3 Execution timed out 7 ms 6136 KB Time limit exceeded (wall clock)
4 Correct 13 ms 6264 KB Output is correct
5 Correct 19 ms 6136 KB Output is correct
6 Execution timed out 8 ms 6264 KB Time limit exceeded (wall clock)
7 Correct 44 ms 6264 KB Output is correct
8 Correct 46 ms 6264 KB Output is correct
9 Correct 75 ms 6648 KB Output is correct
10 Correct 108 ms 6776 KB Output is correct
11 Correct 102 ms 6904 KB Output is correct
12 Correct 139 ms 7324 KB Output is correct
13 Correct 183 ms 7120 KB Output is correct
14 Correct 226 ms 7672 KB Output is correct
15 Correct 254 ms 9464 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1487 ms 9948 KB Output is correct
2 Correct 1594 ms 8952 KB Output is correct
3 Correct 2255 ms 11412 KB Output is correct
4 Execution timed out 19 ms 7656 KB Time limit exceeded (wall clock)
5 Execution timed out 23 ms 8744 KB Time limit exceeded (wall clock)
6 Execution timed out 32 ms 8744 KB Time limit exceeded (wall clock)
7 Execution timed out 211 ms 9852 KB Time limit exceeded (wall clock)
8 Execution timed out 835 ms 15340 KB Time limit exceeded (wall clock)
9 Execution timed out 85 ms 14268 KB Time limit exceeded (wall clock)
10 Execution timed out 81 ms 17936 KB Time limit exceeded (wall clock)
11 Execution timed out 113 ms 14096 KB Time limit exceeded (wall clock)
12 Execution timed out 160 ms 15480 KB Time limit exceeded (wall clock)
13 Execution timed out 94 ms 15352 KB Time limit exceeded (wall clock)
14 Execution timed out 445 ms 16312 KB Time limit exceeded (wall clock)
15 Correct 3274 ms 18952 KB Output is correct
16 Correct 3640 ms 22380 KB Output is correct
17 Execution timed out 143 ms 22600 KB Time limit exceeded (wall clock)