oj.uz

Submission #155488

# Submission time Handle Problem Language Result Execution time Memory
155488 2019-09-28T18:37:22 Z karma Regions (IOI09_regions) C++14
36 / 100
 3548 ms 22376 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 = 700;

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 8 ms 6264 KB Time limit exceeded (wall clock)
2 Execution timed out 8 ms 6264 KB Time limit exceeded (wall clock)
3 Execution timed out 7 ms 6136 KB Time limit exceeded (wall clock)
4 Correct 12 ms 6136 KB Output is correct
5 Correct 15 ms 6136 KB Output is correct
6 Execution timed out 7 ms 6264 KB Time limit exceeded (wall clock)
7 Correct 37 ms 6264 KB Output is correct
8 Correct 45 ms 6392 KB Output is correct
9 Correct 47 ms 6520 KB Output is correct
10 Correct 98 ms 6776 KB Output is correct
11 Correct 124 ms 6904 KB Output is correct
12 Correct 161 ms 7328 KB Output is correct
13 Correct 175 ms 7032 KB Output is correct
14 Correct 163 ms 7504 KB Output is correct
15 Correct 223 ms 9416 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1368 ms 9896 KB Output is correct
2 Correct 1678 ms 9080 KB Output is correct
3 Correct 2149 ms 11384 KB Output is correct
4 Execution timed out 22 ms 7544 KB Time limit exceeded (wall clock)
5 Execution timed out 23 ms 8824 KB Time limit exceeded (wall clock)
6 Execution timed out 28 ms 8596 KB Time limit exceeded (wall clock)
7 Execution timed out 169 ms 9592 KB Time limit exceeded (wall clock)
8 Execution timed out 665 ms 13276 KB Time limit exceeded (wall clock)
9 Execution timed out 81 ms 14200 KB Time limit exceeded (wall clock)
10 Execution timed out 134 ms 17848 KB Time limit exceeded (wall clock)
11 Execution timed out 103 ms 14004 KB Time limit exceeded (wall clock)
12 Execution timed out 168 ms 15476 KB Time limit exceeded (wall clock)
13 Execution timed out 94 ms 15296 KB Time limit exceeded (wall clock)
14 Execution timed out 297 ms 16168 KB Time limit exceeded (wall clock)
15 Correct 3194 ms 18932 KB Output is correct
16 Correct 3548 ms 22376 KB Output is correct
17 Execution timed out 137 ms 22364 KB Time limit exceeded (wall clock)