oj.uz

Submission #155504

# Submission time Handle Problem Language Result Execution time Memory
155504 2019-09-28T19:40:40 Z karma Regions (IOI09_regions) C++14
55 / 100
 2940 ms 54904 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 = 600;

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 7 ms 6264 KB Output is correct
3 Correct 10 ms 6264 KB Output is correct
4 Correct 9 ms 6264 KB Output is correct
5 Correct 11 ms 6264 KB Output is correct
6 Correct 18 ms 6264 KB Output is correct
7 Correct 42 ms 6264 KB Output is correct
8 Correct 43 ms 6264 KB Output is correct
9 Correct 32 ms 6648 KB Output is correct
10 Correct 65 ms 6708 KB Output is correct
11 Correct 144 ms 6936 KB Output is correct
12 Correct 149 ms 7328 KB Output is correct
13 Correct 139 ms 7064 KB Output is correct
14 Correct 243 ms 7464 KB Output is correct
15 Correct 225 ms 9464 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 20600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1200 ms 18996 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 224 ms 7676 KB Output is correct
5 Correct 410 ms 8836 KB Output is correct
6 Correct 849 ms 8568 KB Output is correct
7 Correct 1236 ms 9592 KB Output is correct
8 Correct 1143 ms 13432 KB Output is correct
9 Correct 1796 ms 14328 KB Output is correct
10 Correct 2545 ms 17872 KB Output is correct
11 Correct 2940 ms 14084 KB Output is correct
12 Runtime error 163 ms 31976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 141 ms 32412 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 174 ms 36752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 141 ms 41160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 142 ms 51880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 171 ms 54904 KB Execution killed with signal 11 (could be triggered by violating memory limits)