Submission #511176

# Submission time Handle Problem Language Result Execution time Memory
511176 2022-01-15T10:49:30 Z 600Mihnea Regions (IOI09_regions) C++17
0 / 100
9 ms 14384 KB
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 2e5 + 7;
const int M = 500;
int n;
int r;
int q;
int par[N];
int type[N];
vector<int> g[N];
vector<int> pos[N];
vector<int> verts[N];
int low[N];
int high[N];
int top;

void build(int a) {
  low[a] = ++top;
  verts[type[a]].push_back(a);
  pos[type[a]].push_back(top);
  for (auto &b : g[a]) {
    build(b);
  }
  high[a] = top;
}

int getcnt(int prefix, int value) {
  int sol = 0, low = 0, high = (int) pos[value].size() - 1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (pos[value][mid] <= prefix) {
      sol = mid + 1;
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return sol;
}

signed main() {
  freopen ("input", "r", stdin);

  cin >> n >> r >> q;
  cin >> type[1];
  for (int i = 2; i <= n; i++) {
    cin >> par[i] >> type[i];
    g[par[i]].push_back(i);
  }
  build(1);
  for (int iq = 1; iq <= q; iq++) {
    int a, b;
    cin >> a >> b;
    int sol = 0;
    for (auto &v : verts[a]) {
      sol += getcnt(high[v], b) - getcnt(low[v] - 1, b);
    }
    cout << sol << endl;
  }
  return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:44:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   freopen ("input", "r", stdin);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14280 KB Unexpected end of file - int32 expected
2 Incorrect 7 ms 14384 KB Unexpected end of file - int32 expected
3 Incorrect 6 ms 14280 KB Unexpected end of file - int32 expected
4 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
5 Incorrect 8 ms 14352 KB Unexpected end of file - int32 expected
6 Incorrect 7 ms 14336 KB Unexpected end of file - int32 expected
7 Incorrect 8 ms 14280 KB Unexpected end of file - int32 expected
8 Incorrect 8 ms 14280 KB Unexpected end of file - int32 expected
9 Incorrect 8 ms 14280 KB Unexpected end of file - int32 expected
10 Incorrect 6 ms 14280 KB Unexpected end of file - int32 expected
11 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
12 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
13 Incorrect 7 ms 14296 KB Unexpected end of file - int32 expected
14 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
15 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
2 Incorrect 7 ms 14344 KB Unexpected end of file - int32 expected
3 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
4 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
5 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
6 Incorrect 7 ms 14272 KB Unexpected end of file - int32 expected
7 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
8 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
9 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
10 Incorrect 7 ms 14364 KB Unexpected end of file - int32 expected
11 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
12 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
13 Incorrect 7 ms 14280 KB Unexpected end of file - int32 expected
14 Incorrect 9 ms 14280 KB Unexpected end of file - int32 expected
15 Incorrect 8 ms 14280 KB Unexpected end of file - int32 expected
16 Incorrect 7 ms 14352 KB Unexpected end of file - int32 expected
17 Incorrect 7 ms 14284 KB Unexpected end of file - int32 expected