oj.uz

Submission #155498

# Submission time Handle Problem Language Result Execution time Memory
155498 2019-09-28T19:16:18 Z karma Regions (IOI09_regions) C++14
9 / 100
 6653 ms 131076 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 = 0;

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

void DFS(int u) {
     in[r[u]].pb(++Time);
     for(int v: a[u]) DFS(v);
     out[r[u]].pb(Time);
}

void GetAns(int u) {
     for(int i = 0; i < cur; ++i) ans[i][r[u] - 1] += cnt[rev[i]];
     ++cnt[r[u]];
     for(int v: a[u]) GetAns(v);
     --cnt[r[u]];
}

void GetRans(int u, int e) {
     cnt[u] = 0;
     for(int v: a[u]) {
        GetRans(v, e);
        cnt[u] += cnt[v];
     }
     rans[pos[e]][r[u] - 1] += cnt[u];
     cnt[u] += (r[u] == e);
}

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) rev[pos[i] = cur ++] = i;
    }
    ans.resize(cur), rans.resize(cur);
    for(int i = 0; i < cur; ++i) ans[i].resize(R), rans[i].resize(R);
    GetAns(1);
    for(int i = 0; i < cur; ++i) GetRans(1, rev[i]);
    while(Q --) {
        cin >> e1 >> e2;
        if(in[e2].empty()) {cout << "0\n"; continue;}
        if(int(in[e1].size()) <= Irene && int(in[e2].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(in[e2].size() > Irene) cout << rans[pos[e2]][e1 - 1] << '\n';
          else cout << ans[pos[e1]][e2 - 1] << '\n';
        }
        cout.flush();
    }
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Execution timed out 7 ms 6184 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 13 ms 6264 KB Output is correct
5 Correct 17 ms 6264 KB Output is correct
6 Execution timed out 13 ms 6820 KB Time limit exceeded (wall clock)
7 Correct 45 ms 6396 KB Output is correct
8 Correct 60 ms 6648 KB Output is correct
9 Correct 79 ms 7476 KB Output is correct
10 Correct 277 ms 8184 KB Output is correct
11 Correct 303 ms 7592 KB Output is correct
12 Correct 408 ms 9132 KB Output is correct
13 Correct 560 ms 8084 KB Output is correct
14 Incorrect 499 ms 7932 KB Output isn't correct
15 Incorrect 376 ms 10664 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1155 ms 10896 KB Output isn't correct
2 Runtime error 910 ms 19716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 1270 ms 25808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Execution timed out 6653 ms 120816 KB Time limit exceeded (wall clock)
5 Execution timed out 4880 ms 123100 KB Time limit exceeded (wall clock)
6 Runtime error 165 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 167 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 161 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 207 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 200 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 207 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 214 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 199 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 215 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 198 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 190 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 190 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)