oj.uz

Submission #155505

# Submission time Handle Problem Language Result Execution time Memory
155505 2019-09-28T19:41:57 Z karma Regions (IOI09_regions) C++14
55 / 100
 2967 ms 54388 KB 
#include<bits/stdc++.h>
#define Task     "test"
#define pb       emplace_back

using namespace std;

const int N = int(2e5) + 2;
const int C = 25002;
const int Irene = 700;

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, ++cur;
    }
    ans.resize(cur), rans.resize(cur);
    for(int i = 0; i < cur; ++i) ans[i].resize(R, 0), rans[i].resize(R, 0);
    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"; cout.flush(); 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:64:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
              while(p < in[e2].size() && in[e2][p] < v) ++p;
                    ~~^~~~~~~~~~~~~~~
regions.cpp:69: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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6136 KB Output is correct
2 Correct 8 ms 6136 KB Output is correct
3 Correct 10 ms 6264 KB Output is correct
4 Correct 11 ms 6136 KB Output is correct
5 Correct 18 ms 6136 KB Output is correct
6 Correct 26 ms 6228 KB Output is correct
7 Correct 29 ms 6264 KB Output is correct
8 Correct 46 ms 6268 KB Output is correct
9 Correct 61 ms 6520 KB Output is correct
10 Correct 109 ms 6776 KB Output is correct
11 Correct 120 ms 6936 KB Output is correct
12 Correct 152 ms 7288 KB Output is correct
13 Correct 146 ms 7060 KB Output is correct
14 Correct 235 ms 7544 KB Output is correct
15 Correct 191 ms 9412 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 20476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1091 ms 19004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 59 ms 24568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Correct 307 ms 7672 KB Output is correct
5 Correct 389 ms 8844 KB Output is correct
6 Correct 815 ms 8616 KB Output is correct
7 Correct 1147 ms 9592 KB Output is correct
8 Correct 1014 ms 13304 KB Output is correct
9 Correct 1509 ms 14376 KB Output is correct
10 Correct 2391 ms 17912 KB Output is correct
11 Correct 2967 ms 14080 KB Output is correct
12 Runtime error 159 ms 32096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 142 ms 32636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 172 ms 36544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 143 ms 41080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 143 ms 51884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 164 ms 54388 KB Execution killed with signal 11 (could be triggered by violating memory limits)