oj.uz

Submission #74083

# Submission time Handle Problem Language Result Execution time Memory
74083 2018-08-30T03:53:31 Z funcsr Regions (IOI09_regions) C++17
100 / 100
 3650 ms 89680 KB 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
const int B = 200;

int N, K, Q;
int ord[200000];
vector<int> G[200000];
int L[200000], R[200000];
vector<int> U[200000];
vector<int> tour[200000];
vector<int> pre[200000];
int TT[2000000];

void dfs(int x, int &size) {
  L[x] = size++;
  tour[ord[x]].pb(L[x]);
  for (int t : G[x]) dfs(t, size);
  R[x] = size-1;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> K >> Q;
  rep(i, N) {
    if (i != 0) {
      int p; cin >> p; p--;
      G[p].pb(i);
    }
    cin >> ord[i];
    ord[i]--;
    U[ord[i]].pb(i);
  }
  int k = 0;
  dfs(0, k);
  rep(g, K) if (U[g].size() >= B) {
    pre[g] = vector<int>(K, 0);
    rep(i, N) TT[i] = 0;
    for (int e1 : U[g]) TT[L[e1]]++, TT[R[e1]+1]--;
    rep(i, N-1) TT[i+1] += TT[i];
    rep(i, N) pre[g][ord[i]] += TT[L[i]];
  }


  rep(_, Q) {
    int r1, r2;
    cin >> r1 >> r2;
    r1--, r2--;
    long long s = 0;
    if (!pre[r1].empty()) s = pre[r1][r2];
    else {
      for (int e1 : U[r1]) s += index(tour[r2], R[e1]+1)-index(tour[r2], L[e1]);
    }
    cout << s << endl;
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19064 KB Output is correct
2 Correct 19 ms 19140 KB Output is correct
3 Correct 21 ms 19160 KB Output is correct
4 Correct 17 ms 19204 KB Output is correct
5 Correct 25 ms 19280 KB Output is correct
6 Correct 23 ms 19484 KB Output is correct
7 Correct 46 ms 19484 KB Output is correct
8 Correct 40 ms 19504 KB Output is correct
9 Correct 47 ms 19888 KB Output is correct
10 Correct 92 ms 19888 KB Output is correct
11 Correct 154 ms 20144 KB Output is correct
12 Correct 139 ms 20660 KB Output is correct
13 Correct 199 ms 20660 KB Output is correct
14 Correct 356 ms 20916 KB Output is correct
15 Correct 341 ms 23600 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1308 ms 24240 KB Output is correct
2 Correct 684 ms 24240 KB Output is correct
3 Correct 1014 ms 26416 KB Output is correct
4 Correct 274 ms 26416 KB Output is correct
5 Correct 344 ms 26416 KB Output is correct
6 Correct 474 ms 26416 KB Output is correct
7 Correct 1020 ms 26416 KB Output is correct
8 Correct 961 ms 32688 KB Output is correct
9 Correct 2095 ms 35232 KB Output is correct
10 Correct 2308 ms 71088 KB Output is correct
11 Correct 2029 ms 88240 KB Output is correct
12 Correct 1498 ms 88240 KB Output is correct
13 Correct 1992 ms 88240 KB Output is correct
14 Correct 2450 ms 88240 KB Output is correct
15 Correct 3650 ms 88240 KB Output is correct
16 Correct 1815 ms 89680 KB Output is correct
17 Correct 2852 ms 89680 KB Output is correct