oj.uz

Submission #656236

# Submission time Handle Problem Language Result Execution time Memory
656236 2022-11-06T15:35:19 Z 600Mihnea Inside information (BOI21_servers) C++17
52.5 / 100
 3500 ms 116176 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;

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) {
    assert(curpar[a] == p);
    for (auto &T : cq[a]) {
      if (!is) {
        continue;
      }
      sol[T] += (send < T);

      for (auto &some : all) {
        if (send < some.start && some.finish < T) {
          sol[T]++;
        }
      }
    }
  }
}

void cdecomp(int a) {
  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);
    }
  }

  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:280:23: warning: unused variable 'i' [-Wunused-variable]
  280 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp: In function 'int main()':
servers.cpp:383:13: warning: unused variable 'INF' [-Wunused-variable]
  383 |   const int INF = (int)1e9 + 7;
      |             ^~~
servers.cpp:292:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  292 |     freopen("___input___.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 31820 KB Output is correct
2 Correct 65 ms 34128 KB Output is correct
3 Correct 65 ms 34056 KB Output is correct
4 Correct 70 ms 34288 KB Output is correct
5 Correct 80 ms 34136 KB Output is correct
6 Correct 63 ms 33948 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 57 ms 31820 KB Output is correct
2 Correct 65 ms 34128 KB Output is correct
3 Correct 65 ms 34056 KB Output is correct
4 Correct 70 ms 34288 KB Output is correct
5 Correct 80 ms 34136 KB Output is correct
6 Correct 63 ms 33948 KB Output is correct
7 Correct 48 ms 31820 KB Output is correct
8 Correct 65 ms 34196 KB Output is correct
9 Correct 235 ms 34156 KB Output is correct
10 Correct 66 ms 34380 KB Output is correct
11 Correct 64 ms 34252 KB Output is correct
12 Correct 620 ms 34036 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31840 KB Output is correct
2 Correct 306 ms 99964 KB Output is correct
3 Correct 276 ms 99904 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31840 KB Output is correct
2 Correct 306 ms 99964 KB Output is correct
3 Correct 276 ms 99904 KB Output is correct
4 Correct 51 ms 31792 KB Output is correct
5 Execution timed out 3550 ms 90636 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31820 KB Output is correct
2 Correct 366 ms 114120 KB Output is correct
3 Correct 370 ms 114264 KB Output is correct
4 Correct 279 ms 114496 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31820 KB Output is correct
2 Correct 366 ms 114120 KB Output is correct
3 Correct 370 ms 114264 KB Output is correct
4 Correct 279 ms 114496 KB Output is correct
5 Correct 46 ms 31736 KB Output is correct
6 Correct 398 ms 116128 KB Output is correct
7 Execution timed out 3554 ms 108952 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31820 KB Output is correct
2 Correct 280 ms 97168 KB Output is correct
3 Correct 299 ms 96252 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31820 KB Output is correct
2 Correct 280 ms 97168 KB Output is correct
3 Correct 299 ms 96252 KB Output is correct
4 Correct 54 ms 31820 KB Output is correct
5 Execution timed out 3571 ms 88136 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 31784 KB Output is correct
2 Correct 336 ms 114144 KB Output is correct
3 Correct 339 ms 114144 KB Output is correct
4 Correct 302 ms 114544 KB Output is correct
5 Correct 49 ms 31820 KB Output is correct
6 Correct 277 ms 97264 KB Output is correct
7 Correct 340 ms 96228 KB Output is correct
8 Correct 409 ms 97908 KB Output is correct
9 Correct 448 ms 97708 KB Output is correct
10 Correct 488 ms 103332 KB Output is correct
11 Correct 485 ms 102068 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 31784 KB Output is correct
2 Correct 336 ms 114144 KB Output is correct
3 Correct 339 ms 114144 KB Output is correct
4 Correct 302 ms 114544 KB Output is correct
5 Correct 49 ms 31820 KB Output is correct
6 Correct 277 ms 97264 KB Output is correct
7 Correct 340 ms 96228 KB Output is correct
8 Correct 409 ms 97908 KB Output is correct
9 Correct 448 ms 97708 KB Output is correct
10 Correct 488 ms 103332 KB Output is correct
11 Correct 485 ms 102068 KB Output is correct
12 Correct 48 ms 31860 KB Output is correct
13 Correct 369 ms 116176 KB Output is correct
14 Execution timed out 3540 ms 108620 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31828 KB Output is correct
2 Correct 69 ms 34032 KB Output is correct
3 Correct 64 ms 33996 KB Output is correct
4 Correct 67 ms 34252 KB Output is correct
5 Correct 60 ms 34104 KB Output is correct
6 Correct 63 ms 33868 KB Output is correct
7 Correct 56 ms 31828 KB Output is correct
8 Correct 281 ms 99928 KB Output is correct
9 Correct 290 ms 99968 KB Output is correct
10 Correct 53 ms 31824 KB Output is correct
11 Correct 369 ms 114100 KB Output is correct
12 Correct 340 ms 114252 KB Output is correct
13 Correct 323 ms 114636 KB Output is correct
14 Correct 51 ms 31864 KB Output is correct
15 Correct 265 ms 97160 KB Output is correct
16 Correct 314 ms 96228 KB Output is correct
17 Correct 450 ms 97744 KB Output is correct
18 Correct 417 ms 97800 KB Output is correct
19 Correct 476 ms 103276 KB Output is correct
20 Correct 539 ms 102092 KB Output is correct
21 Correct 282 ms 98796 KB Output is correct
22 Correct 290 ms 98768 KB Output is correct
23 Correct 358 ms 98212 KB Output is correct
24 Correct 356 ms 98132 KB Output is correct
25 Correct 581 ms 103656 KB Output is correct
26 Correct 426 ms 95840 KB Output is correct
27 Correct 387 ms 95436 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31828 KB Output is correct
2 Correct 69 ms 34032 KB Output is correct
3 Correct 64 ms 33996 KB Output is correct
4 Correct 67 ms 34252 KB Output is correct
5 Correct 60 ms 34104 KB Output is correct
6 Correct 63 ms 33868 KB Output is correct
7 Correct 56 ms 31828 KB Output is correct
8 Correct 281 ms 99928 KB Output is correct
9 Correct 290 ms 99968 KB Output is correct
10 Correct 53 ms 31824 KB Output is correct
11 Correct 369 ms 114100 KB Output is correct
12 Correct 340 ms 114252 KB Output is correct
13 Correct 323 ms 114636 KB Output is correct
14 Correct 51 ms 31864 KB Output is correct
15 Correct 265 ms 97160 KB Output is correct
16 Correct 314 ms 96228 KB Output is correct
17 Correct 450 ms 97744 KB Output is correct
18 Correct 417 ms 97800 KB Output is correct
19 Correct 476 ms 103276 KB Output is correct
20 Correct 539 ms 102092 KB Output is correct
21 Correct 282 ms 98796 KB Output is correct
22 Correct 290 ms 98768 KB Output is correct
23 Correct 358 ms 98212 KB Output is correct
24 Correct 356 ms 98132 KB Output is correct
25 Correct 581 ms 103656 KB Output is correct
26 Correct 426 ms 95840 KB Output is correct
27 Correct 387 ms 95436 KB Output is correct
28 Correct 52 ms 31740 KB Output is correct
29 Correct 69 ms 34160 KB Output is correct
30 Correct 243 ms 34156 KB Output is correct
31 Correct 67 ms 34340 KB Output is correct
32 Correct 66 ms 34236 KB Output is correct
33 Correct 630 ms 33964 KB Output is correct
34 Correct 50 ms 31824 KB Output is correct
35 Execution timed out 3554 ms 90688 KB Time limit exceeded
36 Halted 0 ms 0 KB -