— Dark mode

Aalto Competitive Programming 2025 - wk7 Homework

Company Queries II

  • Start: 2025-10-08 20:00:00
  • End: 2025-10-23 20:00:00
Submission details
Task:Company Queries II
Sender:ileska
Submission time:2025-10-21 23:08:59 +0300
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.73 sdetails
#7ACCEPTED0.46 sdetails
#80.56 sdetails
#90.74 sdetails
#100.67 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.77 sdetails

Code

#include <bits/stdc++.h>
#include <chrono>
#include <vector>

#define ll long long

struct Emp {
  ll bossNum;
  ll height;
};
struct Qq {
  ll q0;
  ll q1;
};
std::ostream &operator<<(std::ostream &os, const std::vector<Qq> &v) {
  os << "[";
  for (long unsigned int i = 0; i < v.size(); ++i) {
    os << "(";
    os << v[i].q0;
    os << ", ";
    os << v[i].q1;
    os << ")";
    if (i != v.size() - 1)
      os << ", ";
  }
  os << "]";
  return os;
}

std::ostream &operator<<(std::ostream &os, const std::vector<Emp> &v) {
  os << "[";
  for (long unsigned int i = 0; i < v.size(); ++i) {
    os << v[i].bossNum;
    if (i != v.size() - 1)
      os << ", ";
  }
  os << "]";
  return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  os << "[";
  for (long unsigned int i = 0; i < v.size(); ++i) {
    os << v[i];
    if (i != v.size() - 1)
      os << ", ";
  }
  os << "]";
  return os;
}

void printMap(std::vector<ll> &parentMap, ll empCount, ll logHeight) {
  for (int hh = 0; hh < logHeight; hh++) {
    for (int ee = 0; ee < empCount; ee++) {
      std::cout << std::setw(2) << parentMap[ee + hh * empCount] << " ";
    }
    std::cout << std::endl;
  }
}

ll nthBossFast(ll emp, ll nth, ll empCount, std::vector<ll> &bossMap) {
  if (nth == 0) {
    return emp;
  }
  // emp = bossMap[emp + empCount * ii];
  ll ret;
  ll logHH = (ll)std::log2f(nth);
  // std::cout << "123: " << emp << std::endl;
  if (nth == 1) {
    return bossMap[emp];
  } else if (nth == 2) {
    return bossMap[1 * empCount + emp];
  } else {
    ll next = bossMap[logHH * empCount + emp];
    if (next == -1) {
      return 0;
    }
    ret = nthBossFast(next, nth - (1 << logHH), empCount, bossMap);
  }
  return ret;
}
ll nthBossSlow(std::vector<ll> &bosses, ll emp, ll nth) {
  if (nth == 0) {
    return emp;
  }
  ll ret = nthBossSlow(bosses, bosses[emp], nth - 1);
  return ret;
}

ll runSlow(ll q0, ll q1, std::vector<ll> &bosses, std::vector<ll> &heights) {
  ll ret = -2;
  if (q0 == q1) {
    ret = q0;
  } else if (heights[q0] == heights[q1]) {
    if (bosses[q0] == bosses[q1]) {
      ret = bosses[q0];
    } else {
      q0 = bosses[q0];
      q1 = bosses[q1];
    }
  } else if (heights[q0] > heights[q1]) {
    if (bosses[q0] == q1) {
      ret = q1;
    } else {
      q0 = bosses[q0];
      q1 = q1;
    }
  } else {
    if (q0 == bosses[q1]) {
      ret = q0;
    } else {
      q0 = q0;
      q1 = bosses[q1];
    }
  }
  if (ret == -2) {
    ret = runSlow(q0, q1, bosses, heights);
  }
  return ret;
}

ll runFastWhenEqual(ll q0, ll q1, ll empCount, std::vector<ll> &bosses,
                    std::vector<ll> &bossMap, std::vector<ll> &heights) {
  if (q0 == q1) {
    return q0;
  }
  // std::cout << "Pöö " << q0 << " " << q1 << std::endl;
  ll counter = 0;
  ll nextQ0;
  ll nextQ1;
  while (
      counter * empCount < (ll)bossMap.size() &&
      (bossMap[counter * empCount + q0] != bossMap[counter * empCount + q1])) {
    nextQ0 = bossMap[counter * empCount + q0];
    nextQ1 = bossMap[counter * empCount + q1];
    counter++;
  }
  if (counter * empCount >= (ll)bossMap.size()) {
    return 0;
  } else if (counter == 0) {
    return bossMap[0 * empCount + q0];
  } else if (counter == 1) {
    return bossMap[1 * empCount + q0];
  }

  return runFastWhenEqual(nextQ0, nextQ1, empCount, bosses, bossMap, heights);
}

ll runFast(ll q0, ll q1, ll empCount, std::vector<ll> &bosses,
           std::vector<ll> &bossMap, std::vector<ll> &heights) {
  if (heights[q0] > heights[q1]) {
    q0 = nthBossFast(q0, heights[q0] - heights[q1], empCount, bossMap);
    q1 = q1;
  } else if (heights[q0] < heights[q1]) {
    q0 = q0;
    q1 = nthBossFast(q1, heights[q1] - heights[q0], empCount, bossMap);
  }
  return runFastWhenEqual(q0, q1, empCount, bosses, bossMap, heights);
}

int main() {
  ll empCount, qCount;
  std::cin >> empCount;
  std::cin >> qCount;

  // std::vector<Emp> inputNums(empCount, {-1, -1});
  std::vector<ll> bosses(empCount, -1);
  std::vector<ll> heights(empCount, -1);
  bosses[0] = 0;

  for (ll ii = 0; ii < empCount - 1; ii++) {
    ll boss;
    std::cin >> boss;
    bosses[ii + 1] = boss - 1;
  }
  char debugBossMap = 0;
  char debugNthBoss = 0;
  char debugReal = 0;

  // std::cerr << "Starting to create heightMap" << std::endl;
  for (ll ii = 0; ii < empCount; ii++) {
    ll kk = ii;
    ll hh = 0;
    while (kk != 0) {
      kk = bosses[kk];
      if (heights[kk] != -1) {
        hh += heights[kk] + 1;
        break;
      }
      hh += 1;
    }
    heights[ii] = hh;
  }
  // std::cerr << "Stopped to creating heightMap" << std::endl;

  std::vector<std::pair<ll, ll>> queryes(qCount);
  for (ll ii = 0; ii < qCount; ii++) {
    ll q0;
    ll q1;
    std::cin >> q0;
    std::cin >> q1;
    queryes[ii].first = q0 - 1;  // (q0 < q1) ? (q0 - 1) : (q1 - 1);
    queryes[ii].second = q1 - 1; // (q0 < q1) ? (q1 - 1) : (q0 - 1);
  }

  ll maxHeight = *std::max_element(heights.begin(), heights.end());
  ll logHeight = std::ceil(std::log2f(maxHeight + 1));
  std::cerr << "Max height " << maxHeight << " " << logHeight << std::endl;

  std::vector<ll> bossMapFast(empCount * logHeight, -1);
  // std::cerr << (double)emp / (double)empCount << std::endl;
  for (ll emp = 0; emp < empCount; emp++) {
    bossMapFast[emp] = bosses[emp];
  }
  for (ll hh = 1; hh < logHeight; hh++) {
    for (ll emp = 1; emp < empCount; emp++) {
      ll boss = bosses[emp];
      // boss = bossMapFast[(hh - 1) * empCount + boss];
      for (ll kk = 0; kk < hh; kk++) {
        if (boss == 0) {
          break;
        }
        boss = bossMapFast[(hh - kk - 1) * empCount + boss];
      }
      bossMapFast[hh * empCount + emp] = boss;
    }
    // printMap(bossMapFast, empCount, logHeight);
    // std::cout << std::endl;
  }

  if (debugBossMap) {
    std::vector<ll> bossMapSlow(empCount * logHeight, -1);

    for (ll hh = 0; hh < logHeight; hh++) {
      for (ll emp = 1; emp < empCount; emp++) {
        ll boss = emp;
        for (ll kk = 0; kk < (1 << (hh)); kk++) {
          // if (boss == 0) {
          //   break;
          // }
          boss = bosses[boss];
        }
        bossMapSlow[hh * empCount + emp] = boss;
      }
    }
    printMap(bossMapSlow, empCount, logHeight);
    std::cout << std::endl;
    printMap(bossMapFast, empCount, logHeight);
    return 0;
  }

  // return 0;
  // std::cerr << "123" << std::endl;

  if (debugNthBoss) {

    // ll slowTimeSum = 0;
    // ll fastTimeSum = 0;

    // auto start = std::chrono::high_resolution_clock::now();
    ll emp = queryes[0].first;
    ll nthBossNro = queryes[0].second % 20;
    ll slow = nthBossSlow(bosses, emp, nthBossNro);
    // auto slowTime = std::chrono::high_resolution_clock::now();

    ll fast = nthBossFast(emp, nthBossNro, empCount, bossMapFast);
    // auto fastTime = std::chrono::high_resolution_clock::now();
    // slowTimeSum +=
    //     std::chrono::duration_cast<std::chrono::nanoseconds>(slowTime -
    //     start)
    //         .count();
    // fastTimeSum += std::chrono::duration_cast<std::chrono::nanoseconds>(
    //                    fastTime - slowTime)
    //                    .count();
    if (slow != fast) {
      std::cerr << "Searching the " << nthBossNro << " boss for employee "
                << emp << std::endl;
      std::cerr << slow + 1 << " " << fast + 1 << std::endl;
      std::cout << "BROKENG" << std::endl;
    }
    // std::cout << slowTimeSum << " " << fastTimeSum << std::endl;
    return 0;
  }

  if (debugReal) {
    std::cerr << "started " << qCount << std::endl;

    ll slowTimeSum = 0;
    ll fastTimeSum = 0;

    for (int ii = 0; ii < qCount; ii++) {
      ll q0 = queryes[ii].first;
      ll q1 = queryes[ii].second;

      auto t0 = std::chrono::high_resolution_clock::now();
      ll slow = runSlow(q0, q1, bosses, heights);
      auto t1 = std::chrono::high_resolution_clock::now();

      ll fast = runFast(q0, q1, empCount, bosses, bossMapFast, heights);
      auto t2 = std::chrono::high_resolution_clock::now();

      // std::cout << "SLOW: " << slow + 1 << std::endl;
      // std::cout << "FAST: " << fast + 1 << std::endl;
      // std::cout << std::endl;
      slowTimeSum +=
          std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count();
      fastTimeSum +=
          std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count();

      if (slow != fast) {
        std::cerr << slow + 1 << " " << fast + 1 << std::endl;
        std::cerr << "BROKENG" << std::endl;
      }
      // if (ii % (qCount / 10) == 0) {
      //   std::cerr << ii << std::endl;
      // }
      // break;
    }
    double ratio = ((double)fastTimeSum) / ((double)slowTimeSum);
    std::cerr << slowTimeSum << " " << fastTimeSum << " " << ratio << std::endl;
    return 0;
  }
  for (int ii = 0; ii < qCount; ii++) {
    ll q0 = queryes[ii].first;
    ll q1 = queryes[ii].second;

    ll fast = runFast(q0, q1, empCount, bosses, bossMapFast, heights);

    std::cout << fast + 1 << std::endl;
  }
}

Test details

Test 1

Verdict: ACCEPTED

input
10 10
1 2 3 4 5 6 7 8 9
6 9
8 10
10 3
...
view save

correct output
6
8
3
1
8
...
view save

user output
6
8
3
1
8
...
view save

Error:
Max height 9 4

Test 2

Verdict: ACCEPTED

input
10 10
1 1 1 1 1 1 1 1 1
1 7
3 4
4 1
...
view save

correct output
1
1
1
1
1
...
view save

user output
1
1
1
1
1
...
view save

Error:
Max height 1 1

Test 3

Verdict: ACCEPTED

input
10 10
1 1 1 1 2 3 4 4 1
1 8
2 7
8 3
...
view save

correct output
1
1
1
1
1
...
view save

user output
1
1
1
1
1
...
view save

Error:
Max height 2 2

Test 4

Verdict: ACCEPTED

input
10 10
1 1 3 1 2 2 5 3 9
7 2
7 6
3 9
...
view save

correct output
2
2
3
1
1
...
view save

user output
2
2
3
1
1
...
view save

Error:
Max height 3 2

Test 5

Verdict: ACCEPTED

input
10 10
1 2 3 2 5 3 2 2 4
6 1
1 3
1 9
...
view save

correct output
1
1
1
2
2
...
view save

user output
1
1
1
2
2
...
view save

Error:
Max height 4 3

Test 6

Verdict: ACCEPTED

input
200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

correct output
74862
8750
16237
72298
58111
...
view save

user output
74862
8750
16237
72298
58111
...
view save

Error:
Max height 199999 18

Test 7

Verdict: ACCEPTED

input
200000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
view save

correct output
1
1
1
1
1
...
view save

user output
1
1
1
1
1
...
view save

Error:
Max height 1 1

Test 8

Verdict:

input
200000 200000
1 2 1 2 3 2 1 6 3 1 10 12 13 4...
view save

correct output
1
2
2
2
1
...
view save

user output
1
2
2
2
1
...
view save

Feedback: Incorrect character on line 932 col 2: expected "12", got "1"
Error:
Max height 30 5

Test 9

Verdict:

input
200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

correct output
2796
633
633
151
2690
...
view save

user output
2796
633
633
151
2690
...
view save

Feedback: Incorrect character on line 25 col 2: expected "151", got "1"
Error:
Max height 13420 14

Test 10

Verdict:

input
200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

correct output
365
73
103
365
216
...
view save

user output
365
73
103
365
216
...
view save

Feedback: Incorrect character on line 2554 col 1: expected "216", got "1"
Error:
Max height 3243 12

Test 11

Verdict: ACCEPTED

input
2 4
1
1 1
1 2
2 1
...
view save

correct output
1
1
1
2
view save

user output
1
1
1
2
view save

Error:
Max height 1 1

Test 12

Verdict: ACCEPTED

input
200000 200000
1 1 2 3 4 5 6 7 8 9 10 11 12 1...
view save

correct output
27468
6353
27468
6353
6353
...
view save

user output
27468
6353
27468
6353
6353
...
view save

Error:
Max height 45511 16

Tasks

A Company Queries IIB Download Speed

Submissions (ileska)

2025-10-21 23:48:59 2025-10-21 23:30:25 2025-10-21 23:08:59 2025-10-21 22:06:02 2025-10-21 18:43:38 2025-10-21 18:33:29 2025-10-21 18:26:47 2025-10-21 18:26:24 2025-10-21 18:08:19 2025-10-21 17:54:06 2025-10-21 15:15:14 2025-10-21 15:06:28 2025-10-21 15:02:08