oj.uz

Submission #155500

# Submission time Handle Problem Language Result Execution time Memory
155500 2019-09-28T19:28:55 Z karma Regions (IOI09_regions) C++14
13 / 100
 7211 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, 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
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6136 KB Output is correct
2 Correct 8 ms 6264 KB Output is correct
3 Correct 10 ms 6136 KB Output is correct
4 Correct 13 ms 6268 KB Output is correct
5 Correct 18 ms 6264 KB Output is correct
6 Correct 38 ms 6776 KB Output is correct
7 Correct 46 ms 6520 KB Output is correct
8 Correct 64 ms 6648 KB Output is correct
9 Correct 112 ms 7416 KB Output is correct
10 Correct 217 ms 8184 KB Output is correct
11 Correct 270 ms 7596 KB Output is correct
12 Correct 463 ms 9212 KB Output is correct
13 Correct 508 ms 8084 KB Output is correct
14 Incorrect 426 ms 8028 KB Output isn't correct
15 Incorrect 440 ms 10664 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1368 ms 10836 KB Output isn't correct
2 Runtime error 996 ms 19600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 1411 ms 25800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 7211 ms 120816 KB Output isn't correct
5 Incorrect 5590 ms 123108 KB Output isn't correct
6 Runtime error 163 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 145 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 151 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 185 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 185 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 206 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 210 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 201 ms 131076 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 203 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 208 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 191 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)