Submission #265273

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
265273	2020-08-14T14:40:51 Z	WLZ	Regions (IOI09_regions)	C++14	95 / 100	8000 ms	29284 KB

regions

#include <bits/stdc++.h>
using namespace std;

int n, r, q, cur = 0;
vector<int> h, s;
vector< vector<int> > g;
vector< vector< pair<int, int> > > reg;

int dfs(int u) {
  int st = cur++;
  int en = st;
  for (auto& v : g[u]) {
    en = dfs(v);
  }
  reg[h[u]].push_back({st, 1});
  reg[h[u]].push_back({en, -1});
  return en;
}

long long solve(int r1, int r2) {
  int cur = 0, idx = -1;
  long long ans = 0;
  for (auto& p : reg[r2]) {
    if (p.second == -1) {
      continue;
    }
    while (idx + 1 < (int) reg[r1].size() && reg[r1][idx + 1].first < p.first) {
      idx++;
      cur += reg[r1][idx].second;
    }
    ans += (long long) cur;
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> r >> q;
  h.resize(n + 1);
  s.resize(n + 1);
  cin >> h[1];
  g.resize(n + 1);
  for (int i = 2; i <= n; i++) {
    cin >> s[i] >> h[i];
    g[s[i]].push_back(i);
  }
  reg.resize(r + 1);
  dfs(1);
  for (int i = 1; i <= r; i++) {
    sort(reg[i].begin(), reg[i].end());
  }
  while (q--) {
    int r1, r2;
    cin >> r1 >> r2;
    cout << solve(r1, r2) << endl;
  }
  return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	7 ms	384 KB	Output is correct
6	Correct	17 ms	512 KB	Output is correct
7	Correct	27 ms	640 KB	Output is correct
8	Correct	30 ms	512 KB	Output is correct
9	Correct	44 ms	1280 KB	Output is correct
10	Correct	75 ms	1276 KB	Output is correct
11	Correct	108 ms	1664 KB	Output is correct
12	Correct	131 ms	2552 KB	Output is correct
13	Correct	125 ms	2296 KB	Output is correct
14	Correct	195 ms	2944 KB	Output is correct
15	Correct	226 ms	6400 KB	Output is correct

Subtask #2

80.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3974 ms	7412 KB	Output is correct
2	Execution timed out	8031 ms	6264 KB	Time limit exceeded
3	Correct	5044 ms	9972 KB	Output is correct
4	Correct	231 ms	3168 KB	Output is correct
5	Correct	367 ms	5248 KB	Output is correct
6	Correct	834 ms	4984 KB	Output is correct
7	Correct	1190 ms	6652 KB	Output is correct
8	Correct	949 ms	13184 KB	Output is correct
9	Correct	1758 ms	15096 KB	Output is correct
10	Correct	2426 ms	20936 KB	Output is correct
11	Correct	3148 ms	16032 KB	Output is correct
12	Correct	4343 ms	16624 KB	Output is correct
13	Correct	5023 ms	17136 KB	Output is correct
14	Correct	7390 ms	17132 KB	Output is correct
15	Correct	4970 ms	22256 KB	Output is correct
16	Correct	4590 ms	29284 KB	Output is correct
17	Correct	5298 ms	28012 KB	Output is correct