oj.uz

Submission #155484

# Submission time Handle Problem Language Result Execution time Memory
155484 2019-09-28T18:27:19 Z karma Regions (IOI09_regions) C++14
36 / 100
 3506 ms 23124 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 r[N], cur, Time = 0;
vector<int> out[C], in[C], a[N], ans[C];
int n, R, Q, p, e1, e2, res = 0;

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[e1][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);
    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(ans[e1].empty()) {
             cur = 0; ans[e1].resize(R, 0); GetAns(1);
          }
          cout << ans[e1][e2 - 1] << '\n';
        }
        cout.flush();
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
              while(p < in[e2].size() && in[e2][p] < v) ++p;
                    ~~^~~~~~~~~~~~~~~
regions.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
              while(p < in[e2].size() && in[e2][p] <= v) ++p;
                    ~~^~~~~~~~~~~~~~~
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
11.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7 ms 6700 KB Time limit exceeded (wall clock)
2 Execution timed out 8 ms 6776 KB Time limit exceeded (wall clock)
3 Execution timed out 8 ms 6776 KB Time limit exceeded (wall clock)
4 Correct 10 ms 6780 KB Output is correct
5 Correct 20 ms 6904 KB Output is correct
6 Execution timed out 10 ms 6904 KB Time limit exceeded (wall clock)
7 Correct 31 ms 6776 KB Output is correct
8 Correct 43 ms 6904 KB Output is correct
9 Correct 59 ms 7160 KB Output is correct
10 Correct 94 ms 7288 KB Output is correct
11 Correct 110 ms 7544 KB Output is correct
12 Correct 146 ms 7928 KB Output is correct
13 Correct 220 ms 7672 KB Output is correct
14 Correct 197 ms 8164 KB Output is correct
15 Correct 260 ms 9996 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1449 ms 10484 KB Output is correct
2 Correct 1724 ms 9684 KB Output is correct
3 Correct 2195 ms 11992 KB Output is correct
4 Execution timed out 20 ms 8184 KB Time limit exceeded (wall clock)
5 Execution timed out 22 ms 9336 KB Time limit exceeded (wall clock)
6 Execution timed out 32 ms 9256 KB Time limit exceeded (wall clock)
7 Execution timed out 233 ms 10232 KB Time limit exceeded (wall clock)
8 Execution timed out 767 ms 15836 KB Time limit exceeded (wall clock)
9 Execution timed out 85 ms 14712 KB Time limit exceeded (wall clock)
10 Execution timed out 81 ms 18340 KB Time limit exceeded (wall clock)
11 Execution timed out 103 ms 14456 KB Time limit exceeded (wall clock)
12 Execution timed out 170 ms 15992 KB Time limit exceeded (wall clock)
13 Execution timed out 98 ms 15836 KB Time limit exceeded (wall clock)
14 Execution timed out 490 ms 16904 KB Time limit exceeded (wall clock)
15 Correct 3157 ms 19428 KB Output is correct
16 Correct 3506 ms 22868 KB Output is correct
17 Execution timed out 145 ms 23124 KB Time limit exceeded (wall clock)