oj.uz

Submission #518377

# Submission time Handle Problem Language Result Execution time Memory
518377 2022-01-23T15:43:16 Z cadmiumsky Regions (IOI09_regions) C++14
12 / 100
 8000 ms 131076 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7368 KB Output isn't correct
2 Correct 5 ms 7368 KB Output is correct
3 Correct 6 ms 7368 KB Output is correct
4 Correct 8 ms 7368 KB Output is correct
5 Correct 11 ms 7368 KB Output is correct
6 Correct 26 ms 7880 KB Output is correct
7 Correct 29 ms 7624 KB Output is correct
8 Correct 46 ms 7752 KB Output is correct
9 Correct 65 ms 8520 KB Output is correct
10 Correct 150 ms 9252 KB Output is correct
11 Correct 138 ms 8712 KB Output is correct
12 Correct 222 ms 10176 KB Output is correct
13 Correct 158 ms 9304 KB Output is correct
14 Execution timed out 8055 ms 9160 KB Time limit exceeded
15 Incorrect 320 ms 11824 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8013 ms 12492 KB Time limit exceeded
2 Execution timed out 8007 ms 11544 KB Time limit exceeded
3 Execution timed out 8019 ms 14672 KB Time limit exceeded
4 Runtime error 77 ms 131076 KB Execution killed with signal 9
5 Runtime error 91 ms 131076 KB Execution killed with signal 9
6 Runtime error 89 ms 131076 KB Execution killed with signal 9
7 Runtime error 118 ms 131076 KB Execution killed with signal 9
8 Runtime error 121 ms 131076 KB Execution killed with signal 9
9 Runtime error 146 ms 131076 KB Execution killed with signal 9
10 Runtime error 153 ms 131076 KB Execution killed with signal 9
11 Runtime error 185 ms 131076 KB Execution killed with signal 9
12 Runtime error 164 ms 131076 KB Execution killed with signal 9
13 Runtime error 176 ms 131076 KB Execution killed with signal 9
14 Runtime error 189 ms 131076 KB Execution killed with signal 9
15 Runtime error 181 ms 131076 KB Execution killed with signal 9
16 Runtime error 174 ms 131076 KB Execution killed with signal 9
17 Runtime error 182 ms 131076 KB Execution killed with signal 9