Submission #518400

#	Time	Username	Problem	Language	Result	Execution time	Memory
518400		cadmiumsky	Regions (IOI09_regions)	C++14	100 / 100	2577 ms	31160 KiB

regions

#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 (stderr)

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 / 15
• Subtask 2: 85 / 85