Submission #518377

#	Time	Username	Problem	Language	Result	Execution time	Memory
518377		cadmiumsky	Regions (IOI09_regions)	C++14	12 / 100	8055 ms	131076 KiB

regions

#include <bits/stdc++.h>

using namespace std;
// ---------------------------------------------------
// ---------------------------------------------------
// ---------------------------------------------------
// BIG - BIG
// BIG - SMALL
// SMALL - BIG
// SMALL - SMALL
const int nmax = 2e5 + 5;
const int rmax = 25e3 + 5;

vector<int> graph[nmax];

int n, r, q;

int discr;
void initdiscr() {discr = sqrt(n);};
int heavy[rmax];
int color[nmax];
int onchain[nmax];
int freq[rmax];
vector<int> biglist;
vector<int> mergelist[rmax];
vector<int> ofcolor[rmax];

vector<int> preqbig[rmax]; 
vector<int> preqsmall[rmax]; 

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

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

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

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[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(),
            [](int a, int b){return abs(a) < abs(b);});
  }
  return;
}

int main() {
  cin >> n >> r >> q;
  initdiscr();
  cin >> color[0];
  freq[--color[0]]++;
  ofcolor[color[0]].push_back(0);
  for(int i = 1, x; i < n; i++) {
    cin >> x >> color[i];
    graph[--x].push_back(i);
    freq[--color[i]]++;
    ofcolor[color[i]].push_back(i);
  }
  
  for(int i = 0; i < r; i++) {
    if(freq[i] <= discr) {
      heavy[i] = 1;
      biglist.push_back(i);
      preqbig[i].resize(r, 0);
      preqsmall[i].resize(r,0);
    }
    else {
      heavy[i] = 0;
    }
  }
  
  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()) {
          if(comp(mergelist[up][ptr[0]], mergelist[down][ptr[1]]))
            depth += mergelist[up][ptr[0]] / abs(mergelist[up][ptr[0]]);
          else {
            if(mergelist[down][ptr[1]] > 0)
              answer += depth;
          }
        }
        break;
      case 1:
        answer = preqsmall[down][up];
        break;
      case 2:
        answer = preqbig[up][down];
        break;
      case 3:
        answer = preqbig[up][down];
        break;
      default:
        answer = -1; 
    }
    
    cout << answer << endl;
  }
}

Compilation message (stderr)

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

• Subtask 1: 12 / 15
• Subtask 2: 0 / 85