oj.uz

Submission #656242

# Submission time Handle Problem Language Result Execution time Memory
656242 2022-11-06T15:44:54 Z 600Mihnea Inside information (BOI21_servers) C++17
67.5 / 100
 3500 ms 118736 KB 
bool home = 0;
#include <bits/stdc++.h>

using namespace std;

const int N = 240000 + 7;
const int K = 20;
int n;
int k;
vector<pair<int, int>> gg[N];
vector<pair<int, int>> q2[N];
int q1[N];
int p[N];
int pskip[K][N];
int dep[N];
int euler_tour[2 * N];
int tour_sz;
int first_time_on_tour[N];
int last_time_on_tour[N];
int lg2[2 * N];
int idup[N];
//vector<int> g[N];
pair<int, int> tab_lca[2 * N][K];
vector<int> who_have_id[N];
int who_has_id[N];

void dfs_lca(int a, int par = 0)
{
  p[a] = par;
  euler_tour[++tour_sz] = a;
  first_time_on_tour[a] = last_time_on_tour[a] = tour_sz;
  vector<pair<int, int>> ngg;
  for (auto& it : gg[a])
  {
    int b = it.first;
    int i = it.second;

    if (b == par) {
      continue;
    }
    ngg.push_back(it);
    who_has_id[i] = b;
    idup[b] = i;
    dep[b] = 1 + dep[a];
    dfs_lca(b, a);
    euler_tour[++tour_sz] = a;
    last_time_on_tour[a] = tour_sz;
  }
  gg[a] = ngg;
}

void lcaTM()
{
  dfs_lca(1);
  for (int i = 2; i <= tour_sz; i++)
  {
    lg2[i] = 1 + lg2[i / 2];
  }
  for (int i = 1; i <= tour_sz; i++)
  {
    tab_lca[i][0] = { dep[euler_tour[i]], euler_tour[i] };
  }
  for (int k = 1; (1 << k) <= tour_sz; k++)
  {
    for (int i = 1; i + (1 << k) - 1 <= tour_sz; i++)
    {
      tab_lca[i][k] = min(tab_lca[i][k - 1], tab_lca[i + (1 << (k - 1))][k - 1]);
    }
  }
}

int lca(int a, int b)
{
  if (first_time_on_tour[a] > last_time_on_tour[b])
  {
    swap(a, b);
  }
  a = first_time_on_tour[a];
  b = last_time_on_tour[b];
  int k = lg2[b - a + 1];
  return min(tab_lca[a][k], tab_lca[b - (1 << k) + 1][k]).second;
}

int goup(int a, int cnt) {
  assert(cnt >= 0);
  for (int i = 0; i < K; i++) {
    if (cnt & (1 << i)) {
      a = pskip[i][a];
    }
  }
  return a;
}

int sol[N];
int tp[N];
int inc[N];
int dcr[N];
int cnt[N];

void dfs2(int a) {
  inc[a] = max(inc[a], 1);
  dcr[a] = max(dcr[a], 1);
  for (auto& it : gg[a]) {
    int b = it.first;
    if (b == p[a]) {
      continue;
    }
    if (idup[a] < idup[b]) {
      inc[b] = 1 + inc[a];
    }
    else {
      dcr[b] = 1 + dcr[a];
    }
    dfs2(b);
  }  ///cout<<"vis "<<a<<" : "<<inc[a]<<" vs "<<dcr[a]<<"\n";
}

bool blocked[N];
vector<int> cq[N];
vector<pair<int, int>> realg[N];
int score[N];
int total_score;
int curpar[N];
int when[N];
int goval[N];

struct T {
  int start;
  int finish;
};

vector<T> all;

void compute_score(int a, int p = -1) {
  score[a] = 1 + (int) cq[a].size();
  for (auto &it : realg[a]) {
    int b = it.first, i = it.second;
    if (blocked[b] || b == p) {
      continue;
    }
    compute_score(b, a);
    score[a] += score[b];
  }
}

int fndcen(int a, int p = -1) {
  int mx = total_score - score[a];
  for (auto &it : realg[a]) {
    int b = it.first, i = it.second;
    if (blocked[b] || b == p) {
      continue;
    }
    mx = max(mx, score[b]);
  }
  if (mx <= total_score / 2) {
    return a;
  }
  for (auto &it : realg[a]) {
    int b = it.first, i = it.second;
    if (blocked[b] || b == p) {
      continue;
    }
    if (mx == score[b]) {
      return fndcen(b, a);
    }
  }
  assert(0);
}

void dfsfromcen(int a, int p, int group, int cr, bool ok, int gval) {
  if (ok) {
    all.push_back({gval, cr});
  }
  curpar[a] = p;
  for (auto &it : realg[a]) {
    int b = it.first, i = it.second;
    if (blocked[b] || b == p) {
      continue;
    }
    when[b] = i;
    bool new_ok = ok;
    if (!(cr < i)) {
      new_ok = 0;
    }
    dfsfromcen(b, a, group, i, new_ok, gval);
  }
}

int kekdfs(int a, int p, int last, int t) {
  int sol = 0;
  for (auto &it : realg[a]) {
    int b = it.first, i = it.second;
    if (blocked[b] || b == p) {
      continue;
    }
    if (last < i) {
      if (i < t) {
        sol++;
      }
      sol += kekdfs(b, a, i, t);
    }
  }
  return sol;
}

vector<int> guys;
vector<pair<int, int>> mag;

void dfsexplore(int a, int p, int lst, bool is, int send) {
  for (auto &it : realg[a]) {
    int b = it.first, i = it.second;
    if (blocked[b] || b == p) {
      continue;
    }
    bool new_is = is;
    if (!(lst > i)) {
      new_is = 0;
    }
    dfsexplore(b, a, i, new_is, send);
  }
  if (p && is) {
    assert(curpar[a] == p);
    for (auto &T : cq[a]) {
      sol[T] += (send < T);

      mag.push_back({T, send});


    }
  }
}

void cdecomp(int a) {
  mag.clear();
  all.clear();
  compute_score(a);
  total_score = score[a];
  a = fndcen(a);

  guys.clear();
  int cnt_guys = 0;
  for (auto &it : realg[a]) {
    int b = it.first, i = it.second;
    if (blocked[b]) {
      continue;
    }
    cnt_guys++;
    when[b] = i;
    goval[b] = i;
    guys.push_back(b);
    dfsfromcen(b, a, i, i, 1, i);
  }
  assert((int) guys.size() == cnt_guys);
  curpar[a] = 0;

  {
    /// the case for a
    for (auto &T : cq[a]) {
      sol[T] += kekdfs(a, 0, -1, T);
    }
  }

  {
    /// the case for the others and it also going through a
    /// it stops at a
    for (auto &it : realg[a]) {
      int b = it.first, i = it.second;
      if (blocked[b]) {
        continue;
      }
      dfsexplore(b, a, i, 1, i);
    }
  }
  sort(all.begin(), all.end(), [&] (T a, T b) {
    return a.finish < b.finish;
  });
  sort(mag.begin(), mag.end());
  int ptr = 0;
  for (auto &lmao : mag) {
    int T = lmao.first, send = lmao.second;
    while (ptr < (int) all.size() && all[ptr].finish < T) {
      ptr++;
    }
    for (int j = 0; j < ptr; j++) {
      if (send < all[j].start) {
        sol[T]++;
      }
    }
  }
  blocked[a] = 1;
  for (auto &it : realg[a]) {
    int b = it.first, i = it.second;
    if (blocked[b]) {
      continue;
    }
    cdecomp(b);
  }
}

int main() {
  if (!home) {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  } else {
    freopen("___input___.txt", "r", stdin);
  }
  cin >> n >> k;
  int cnt3 = 0;
  for (int i = 1; i <= n + k - 1; i++) {
    string s;
    cin >> s;
    assert(s == "S" || s == "Q" || s == "C");
    if (s == "S") {
      tp[i] = 2;
      int a, b;
      cin >> a >> b;
      ///g[a].push_back(b);
      ///g[b].push_back(a);
      gg[a].push_back({ b, i });
      gg[b].push_back({ a, i });
      sol[i] = -1;
    }
    if (s == "Q") {
      int a, b;
      cin >> a >> b;
      if (a == b) {
        tp[i] = 1;
        sol[i] = 1;
      }
      else {
        q2[a].push_back({ b, i });
        tp[i] = 1;
        sol[i] = -2;
      }
    }
    if (s == "C") {
      cnt3++;
      int a;
      cin >> a;
      cq[a].push_back(i);
      ///   cout<<i<<" = "<<a<<"\n";
      q1[i] = a;
      sol[i] = -3;
      tp[i] = 3;
    }
  }
  for (int i = 1; i <= n; i++) {
    realg[i] = gg[i];
  }

  lcaTM();
  dfs2(1);
  cdecomp(1);
  /// solve q1 for the general case

  for (int i = 1; i <= n; i++) {
    pskip[0][i] = p[i];
  }
  for (int k = 1; k < K; k++) {
    for (int i = 1; i <= n; i++) {
      pskip[k][i] = pskip[k - 1][pskip[k - 1][i]];
    }
  }


  for (int a = 1; a <= n; a++) {
    for (auto& it : q2[a]) {
      int b = it.first, i = it.second;
      /**

      **/
      /// drumul de la b la a e crescator?
      vector<int> guys_x, guys_y;
      int x = a, y = b, z;
      swap(x, y);
      z = lca(x, y);
      int last = -1;
      if (y != z) {
        last = idup[y];
      }
      else {
        last = idup[goup(x, dep[x] - dep[z] - 1)];
      }
      bool ok = 1;
      ok &= (inc[y] >= dep[y] - dep[z]);
      ok &= (dcr[x] >= dep[x] - dep[z]);
      if (x != z && y != z) {
        ok &= (idup[goup(x, dep[x] - dep[z] - 1)] <= idup[goup(y, dep[y] - dep[z] - 1)]);
      }
      ok &= (last < i);
      sol[i] = ok;
    }
  }

  const int INF = (int)1e9 + 7;

  int cnt_2 = 0;
  for (int i = 1; i <= n + k - 1 && cnt3 != 0; i++) {
    if (tp[i] == 2) {
      cnt_2++;
      int cnt_down = max(1, inc[who_has_id[i]] - 1);
      int vertex = who_has_id[i];
      for (int j = 1; j <= cnt_down; j++) {
        cnt[vertex]++;
        vertex = p[vertex];
      }
    }
  }
  if (cnt3) {
    assert(cnt_2 == n - 1);
  }
  for (int i = 1; i <= n + k - 1; i++) {
    if (tp[i] == 1) {
      assert(sol[i] == 0 || sol[i] == 1);
      if (sol[i] == 1) {
        cout << "yes\n";
      }
      else {
        cout << "no\n";
      }
    }
    if (tp[i] == 3) {
      cout << sol[i] + 4 << "\n";
    }
  }

  return 0;
}

Compilation message

servers.cpp: In function 'void compute_score(int, int)':
servers.cpp:137:23: warning: unused variable 'i' [-Wunused-variable]
  137 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp: In function 'int fndcen(int, int)':
servers.cpp:149:23: warning: unused variable 'i' [-Wunused-variable]
  149 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp:159:23: warning: unused variable 'i' [-Wunused-variable]
  159 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp: In function 'void cdecomp(int)':
servers.cpp:292:23: warning: unused variable 'i' [-Wunused-variable]
  292 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp: In function 'int main()':
servers.cpp:394:13: warning: unused variable 'INF' [-Wunused-variable]
  394 |   const int INF = (int)1e9 + 7;
      |             ^~~
servers.cpp:304:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  304 |     freopen("___input___.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31820 KB Output is correct
2 Correct 66 ms 34120 KB Output is correct
3 Correct 57 ms 33972 KB Output is correct
4 Correct 65 ms 34264 KB Output is correct
5 Correct 76 ms 34136 KB Output is correct
6 Correct 73 ms 33936 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31820 KB Output is correct
2 Correct 66 ms 34120 KB Output is correct
3 Correct 57 ms 33972 KB Output is correct
4 Correct 65 ms 34264 KB Output is correct
5 Correct 76 ms 34136 KB Output is correct
6 Correct 73 ms 33936 KB Output is correct
7 Correct 52 ms 31820 KB Output is correct
8 Correct 69 ms 34212 KB Output is correct
9 Correct 229 ms 34540 KB Output is correct
10 Correct 74 ms 34264 KB Output is correct
11 Correct 63 ms 34380 KB Output is correct
12 Correct 516 ms 34496 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31876 KB Output is correct
2 Correct 283 ms 99972 KB Output is correct
3 Correct 270 ms 99940 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31876 KB Output is correct
2 Correct 283 ms 99972 KB Output is correct
3 Correct 270 ms 99940 KB Output is correct
4 Correct 57 ms 31868 KB Output is correct
5 Execution timed out 3575 ms 90652 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 31876 KB Output is correct
2 Correct 344 ms 114212 KB Output is correct
3 Correct 362 ms 114124 KB Output is correct
4 Correct 287 ms 114452 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 31876 KB Output is correct
2 Correct 344 ms 114212 KB Output is correct
3 Correct 362 ms 114124 KB Output is correct
4 Correct 287 ms 114452 KB Output is correct
5 Correct 49 ms 31892 KB Output is correct
6 Correct 366 ms 116188 KB Output is correct
7 Correct 3225 ms 116612 KB Output is correct
8 Correct 368 ms 118736 KB Output is correct
9 Correct 375 ms 118624 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31868 KB Output is correct
2 Correct 309 ms 97168 KB Output is correct
3 Correct 307 ms 96208 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31868 KB Output is correct
2 Correct 309 ms 97168 KB Output is correct
3 Correct 307 ms 96208 KB Output is correct
4 Correct 50 ms 31860 KB Output is correct
5 Correct 2757 ms 99608 KB Output is correct
6 Correct 309 ms 98036 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 31820 KB Output is correct
2 Correct 338 ms 114244 KB Output is correct
3 Correct 332 ms 114224 KB Output is correct
4 Correct 328 ms 114472 KB Output is correct
5 Correct 50 ms 31824 KB Output is correct
6 Correct 285 ms 97156 KB Output is correct
7 Correct 305 ms 96408 KB Output is correct
8 Correct 419 ms 97696 KB Output is correct
9 Correct 477 ms 97692 KB Output is correct
10 Correct 552 ms 103244 KB Output is correct
11 Correct 562 ms 102000 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 31820 KB Output is correct
2 Correct 338 ms 114244 KB Output is correct
3 Correct 332 ms 114224 KB Output is correct
4 Correct 328 ms 114472 KB Output is correct
5 Correct 50 ms 31824 KB Output is correct
6 Correct 285 ms 97156 KB Output is correct
7 Correct 305 ms 96408 KB Output is correct
8 Correct 419 ms 97696 KB Output is correct
9 Correct 477 ms 97692 KB Output is correct
10 Correct 552 ms 103244 KB Output is correct
11 Correct 562 ms 102000 KB Output is correct
12 Correct 52 ms 31820 KB Output is correct
13 Correct 479 ms 116228 KB Output is correct
14 Correct 3228 ms 116748 KB Output is correct
15 Correct 369 ms 118636 KB Output is correct
16 Correct 356 ms 118620 KB Output is correct
17 Correct 54 ms 32700 KB Output is correct
18 Correct 2738 ms 102340 KB Output is correct
19 Correct 310 ms 100996 KB Output is correct
20 Correct 403 ms 102460 KB Output is correct
21 Correct 415 ms 102732 KB Output is correct
22 Correct 1881 ms 106640 KB Output is correct
23 Execution timed out 3576 ms 108248 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31856 KB Output is correct
2 Correct 69 ms 34044 KB Output is correct
3 Correct 57 ms 33988 KB Output is correct
4 Correct 66 ms 34308 KB Output is correct
5 Correct 59 ms 34084 KB Output is correct
6 Correct 66 ms 33852 KB Output is correct
7 Correct 49 ms 31760 KB Output is correct
8 Correct 271 ms 99964 KB Output is correct
9 Correct 287 ms 99956 KB Output is correct
10 Correct 45 ms 31792 KB Output is correct
11 Correct 347 ms 114124 KB Output is correct
12 Correct 330 ms 114204 KB Output is correct
13 Correct 287 ms 114508 KB Output is correct
14 Correct 50 ms 31820 KB Output is correct
15 Correct 287 ms 97224 KB Output is correct
16 Correct 293 ms 96152 KB Output is correct
17 Correct 432 ms 97740 KB Output is correct
18 Correct 451 ms 97708 KB Output is correct
19 Correct 475 ms 103216 KB Output is correct
20 Correct 497 ms 102200 KB Output is correct
21 Correct 284 ms 98872 KB Output is correct
22 Correct 287 ms 98876 KB Output is correct
23 Correct 329 ms 98072 KB Output is correct
24 Correct 373 ms 98168 KB Output is correct
25 Correct 471 ms 104668 KB Output is correct
26 Correct 389 ms 95728 KB Output is correct
27 Correct 382 ms 95504 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31856 KB Output is correct
2 Correct 69 ms 34044 KB Output is correct
3 Correct 57 ms 33988 KB Output is correct
4 Correct 66 ms 34308 KB Output is correct
5 Correct 59 ms 34084 KB Output is correct
6 Correct 66 ms 33852 KB Output is correct
7 Correct 49 ms 31760 KB Output is correct
8 Correct 271 ms 99964 KB Output is correct
9 Correct 287 ms 99956 KB Output is correct
10 Correct 45 ms 31792 KB Output is correct
11 Correct 347 ms 114124 KB Output is correct
12 Correct 330 ms 114204 KB Output is correct
13 Correct 287 ms 114508 KB Output is correct
14 Correct 50 ms 31820 KB Output is correct
15 Correct 287 ms 97224 KB Output is correct
16 Correct 293 ms 96152 KB Output is correct
17 Correct 432 ms 97740 KB Output is correct
18 Correct 451 ms 97708 KB Output is correct
19 Correct 475 ms 103216 KB Output is correct
20 Correct 497 ms 102200 KB Output is correct
21 Correct 284 ms 98872 KB Output is correct
22 Correct 287 ms 98876 KB Output is correct
23 Correct 329 ms 98072 KB Output is correct
24 Correct 373 ms 98168 KB Output is correct
25 Correct 471 ms 104668 KB Output is correct
26 Correct 389 ms 95728 KB Output is correct
27 Correct 382 ms 95504 KB Output is correct
28 Correct 52 ms 31836 KB Output is correct
29 Correct 69 ms 34204 KB Output is correct
30 Correct 226 ms 34440 KB Output is correct
31 Correct 67 ms 34348 KB Output is correct
32 Correct 62 ms 34228 KB Output is correct
33 Correct 511 ms 34540 KB Output is correct
34 Correct 48 ms 31940 KB Output is correct
35 Execution timed out 3573 ms 90684 KB Time limit exceeded
36 Halted 0 ms 0 KB -