oj.uz

Submission #518400

# Submission time Handle Problem Language Result Execution time Memory
518400 2022-01-23T16:07:30 Z cadmiumsky Regions (IOI09_regions) C++14
100 / 100
 2577 ms 31160 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// ---------------------------------------------------
// ---------------------------------------------------
// ---------------------------------------------------
// SMALL - SMALL
// SMALL - BIG
// BIG - SMALL
// BIG - BIG
const int nmax = 2e5 + 5;
const int rmax = 25e3 + 5;

vector<int> graph[nmax];

int n, r, q;

int discr;
void initdiscr() {discr = 450;};
bitset<rmax> heavy;
int color[nmax];
int onchain[nmax];
int freq[rmax];
vector<int> biglist;
vector<int> mergelist[rmax];
int preqbig[450][rmax];
int preqsmall[450][rmax];

int ind[rmax];

int pin[nmax], pout[nmax];
int preord[nmax], sum[nmax];
int inp;

// ---------------------------------------------------
// ---------------------------------------------------
// ---------------------------------------------------

static void init23pre(int node) { 
  for(auto x : biglist) {
    preqbig[ind[x]][color[node]] += onchain[x];
    //cout << x << " / " <<  node <<" --> +" << onchain[x] << '>' << preqbig[x][color[node]] << '\n';
  }
  onchain[color[node]]++;
  preord[++inp] = node;
  pin[node] = inp;
  
  for(auto x : graph[node]) {
    init23pre(x);
  }
  onchain[color[node]]--;
  pout[node] = inp;
}

static void init1(int node) {
  for(auto x : biglist) {
    for(int i = 1; i <= n; i++)
      sum[i] = (color[preord[i]] == x) + sum[i - 1];
    for(int i = 0; i < n; i++) {
      if(heavy[color[i]] == 1)
        continue;
      preqsmall[ind[x]][color[i]] += sum[pout[i]] - sum[pin[i] - 1];
    }
  }
}
auto comp = [](int a, int b) {
  return abs(a) < abs(b) || (abs(a) == abs(b) && a < b);
};
static void init0() {
  for(int i = 0; i < n; i++) {
    if(heavy[color[i]]) 
      continue;
    mergelist[color[i]].push_back(pin[i]);
    mergelist[color[i]].push_back(-pout[i] - 1);
  }
  for(int i = 0; i < r; i++) {
    if(heavy[i])
      continue;
    sort(mergelist[i].begin(), mergelist[i].end(),comp);
  }
  return;
}

int main() {
  cin >> n >> r >> q;
  initdiscr();
  cin >> color[0];
  freq[--color[0]]++;
  for(int i = 1, x; i < n; i++) {
    cin >> x >> color[i];
    graph[--x].push_back(i);
    freq[--color[i]]++;
  }
  
  int cnt = 0;
  for(int i = 0; i < r; i++) {
    if(freq[i] >= discr) {
      heavy[i] = 1;
      ind[i] = cnt++;
      biglist.push_back(i);
    }
  }
  
  init23pre(0);
  init1(0);
  init0();
  
  for(int i = 0, up, down; i < q; i++) {
    cin >> up >> down;
    --up;
    --down;
    int answer;
    int ptr[2] = {0, 0};
    int depth = 0;
    switch((heavy[up] << 1) | heavy[down]) {
      case 0:
        answer = 0;
        while(ptr[0] < mergelist[up].size() && 
              ptr[1] < mergelist[down].size()) {
          //cout << mergelist[up][ptr[0]] <<' ' << mergelist[down][ptr[1]] <<'\n';
          if(comp(mergelist[up][ptr[0]], mergelist[down][ptr[1]]))
            depth += mergelist[up][ptr[0]] / abs(mergelist[up][ptr[0]]),
            ptr[0]++;
          else {
            if(mergelist[down][ptr[1]] > 0)
              answer += depth;
            ptr[1]++;
          }
        }
        break;
      case 1:
        answer = preqsmall[ind[down]][up];
        break;
      case 2:
        answer = preqbig[ind[up]][down];
        break;
      case 3:
        answer = preqbig[ind[up]][down];
        break;
      default:
        answer = -1; 
    }
    
    cout << answer << endl;
  }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         while(ptr[0] < mergelist[up].size() &&
      |               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |               ptr[1] < mergelist[down].size()) {
      |               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5576 KB Output is correct
2 Correct 3 ms 5576 KB Output is correct
3 Correct 4 ms 5576 KB Output is correct
4 Correct 7 ms 5576 KB Output is correct
5 Correct 11 ms 5576 KB Output is correct
6 Correct 12 ms 5696 KB Output is correct
7 Correct 20 ms 5576 KB Output is correct
8 Correct 23 ms 5644 KB Output is correct
9 Correct 51 ms 6088 KB Output is correct
10 Correct 45 ms 6088 KB Output is correct
11 Correct 123 ms 6472 KB Output is correct
12 Correct 151 ms 7028 KB Output is correct
13 Correct 230 ms 6728 KB Output is correct
14 Correct 208 ms 7296 KB Output is correct
15 Correct 255 ms 9884 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1143 ms 10576 KB Output is correct
2 Correct 1175 ms 9492 KB Output is correct
3 Correct 1567 ms 12380 KB Output is correct
4 Correct 304 ms 7368 KB Output is correct
5 Correct 290 ms 8984 KB Output is correct
6 Correct 592 ms 12304 KB Output is correct
7 Correct 1113 ms 11216 KB Output is correct
8 Correct 1035 ms 23404 KB Output is correct
9 Correct 1565 ms 15464 KB Output is correct
10 Correct 2273 ms 31160 KB Output is correct
11 Correct 2577 ms 15152 KB Output is correct
12 Correct 1031 ms 17556 KB Output is correct
13 Correct 1519 ms 17740 KB Output is correct
14 Correct 1745 ms 20656 KB Output is correct
15 Correct 2360 ms 21584 KB Output is correct
16 Correct 2136 ms 27200 KB Output is correct
17 Correct 2074 ms 29240 KB Output is correct