oj.uz

Submission #656240

# Submission time Handle Problem Language Result Execution time Memory
656240 2022-11-06T15:41:59 Z 600Mihnea Inside information (BOI21_servers) C++17
62.5 / 100
 3500 ms 116260 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);
    }
  }
  for (auto &lmao : mag) {
    int T = lmao.first, send = lmao.second;
    for (auto &some : all) {
      if (send < some.start && some.finish < T) {
        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:286:23: warning: unused variable 'i' [-Wunused-variable]
  286 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp: In function 'int main()':
servers.cpp:389:13: warning: unused variable 'INF' [-Wunused-variable]
  389 |   const int INF = (int)1e9 + 7;
      |             ^~~
servers.cpp:298:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  298 |     freopen("___input___.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 31820 KB Output is correct
2 Correct 71 ms 34020 KB Output is correct
3 Correct 57 ms 34060 KB Output is correct
4 Correct 65 ms 34252 KB Output is correct
5 Correct 59 ms 34144 KB Output is correct
6 Correct 62 ms 33888 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 31820 KB Output is correct
2 Correct 71 ms 34020 KB Output is correct
3 Correct 57 ms 34060 KB Output is correct
4 Correct 65 ms 34252 KB Output is correct
5 Correct 59 ms 34144 KB Output is correct
6 Correct 62 ms 33888 KB Output is correct
7 Correct 63 ms 31820 KB Output is correct
8 Correct 79 ms 34212 KB Output is correct
9 Correct 229 ms 34432 KB Output is correct
10 Correct 84 ms 34324 KB Output is correct
11 Correct 63 ms 34292 KB Output is correct
12 Correct 535 ms 34608 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31784 KB Output is correct
2 Correct 293 ms 99968 KB Output is correct
3 Correct 324 ms 99880 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31784 KB Output is correct
2 Correct 293 ms 99968 KB Output is correct
3 Correct 324 ms 99880 KB Output is correct
4 Correct 51 ms 31936 KB Output is correct
5 Execution timed out 3574 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 46 ms 31820 KB Output is correct
2 Correct 348 ms 114188 KB Output is correct
3 Correct 343 ms 114340 KB Output is correct
4 Correct 286 ms 114568 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 31820 KB Output is correct
2 Correct 348 ms 114188 KB Output is correct
3 Correct 343 ms 114340 KB Output is correct
4 Correct 286 ms 114568 KB Output is correct
5 Correct 46 ms 31820 KB Output is correct
6 Correct 358 ms 116248 KB Output is correct
7 Execution timed out 3579 ms 105860 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 31820 KB Output is correct
2 Correct 272 ms 97160 KB Output is correct
3 Correct 324 ms 96196 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 31820 KB Output is correct
2 Correct 272 ms 97160 KB Output is correct
3 Correct 324 ms 96196 KB Output is correct
4 Correct 58 ms 31792 KB Output is correct
5 Correct 3247 ms 99412 KB Output is correct
6 Correct 305 ms 100944 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31792 KB Output is correct
2 Correct 376 ms 114128 KB Output is correct
3 Correct 331 ms 114196 KB Output is correct
4 Correct 299 ms 114492 KB Output is correct
5 Correct 51 ms 31748 KB Output is correct
6 Correct 281 ms 97104 KB Output is correct
7 Correct 334 ms 96164 KB Output is correct
8 Correct 423 ms 97808 KB Output is correct
9 Correct 385 ms 97820 KB Output is correct
10 Correct 483 ms 103172 KB Output is correct
11 Correct 500 ms 102200 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31792 KB Output is correct
2 Correct 376 ms 114128 KB Output is correct
3 Correct 331 ms 114196 KB Output is correct
4 Correct 299 ms 114492 KB Output is correct
5 Correct 51 ms 31748 KB Output is correct
6 Correct 281 ms 97104 KB Output is correct
7 Correct 334 ms 96164 KB Output is correct
8 Correct 423 ms 97808 KB Output is correct
9 Correct 385 ms 97820 KB Output is correct
10 Correct 483 ms 103172 KB Output is correct
11 Correct 500 ms 102200 KB Output is correct
12 Correct 57 ms 31824 KB Output is correct
13 Correct 353 ms 116260 KB Output is correct
14 Execution timed out 3560 ms 105880 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 31796 KB Output is correct
2 Correct 69 ms 34124 KB Output is correct
3 Correct 63 ms 34068 KB Output is correct
4 Correct 73 ms 34284 KB Output is correct
5 Correct 62 ms 34140 KB Output is correct
6 Correct 63 ms 33960 KB Output is correct
7 Correct 62 ms 31820 KB Output is correct
8 Correct 280 ms 100020 KB Output is correct
9 Correct 287 ms 100024 KB Output is correct
10 Correct 47 ms 31848 KB Output is correct
11 Correct 354 ms 114164 KB Output is correct
12 Correct 397 ms 114176 KB Output is correct
13 Correct 295 ms 114548 KB Output is correct
14 Correct 50 ms 31824 KB Output is correct
15 Correct 265 ms 97224 KB Output is correct
16 Correct 322 ms 96200 KB Output is correct
17 Correct 404 ms 97740 KB Output is correct
18 Correct 407 ms 97680 KB Output is correct
19 Correct 450 ms 103116 KB Output is correct
20 Correct 533 ms 102204 KB Output is correct
21 Correct 284 ms 98820 KB Output is correct
22 Correct 288 ms 98712 KB Output is correct
23 Correct 347 ms 98284 KB Output is correct
24 Correct 395 ms 98208 KB Output is correct
25 Correct 461 ms 104656 KB Output is correct
26 Correct 436 ms 95800 KB Output is correct
27 Correct 391 ms 95492 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 31796 KB Output is correct
2 Correct 69 ms 34124 KB Output is correct
3 Correct 63 ms 34068 KB Output is correct
4 Correct 73 ms 34284 KB Output is correct
5 Correct 62 ms 34140 KB Output is correct
6 Correct 63 ms 33960 KB Output is correct
7 Correct 62 ms 31820 KB Output is correct
8 Correct 280 ms 100020 KB Output is correct
9 Correct 287 ms 100024 KB Output is correct
10 Correct 47 ms 31848 KB Output is correct
11 Correct 354 ms 114164 KB Output is correct
12 Correct 397 ms 114176 KB Output is correct
13 Correct 295 ms 114548 KB Output is correct
14 Correct 50 ms 31824 KB Output is correct
15 Correct 265 ms 97224 KB Output is correct
16 Correct 322 ms 96200 KB Output is correct
17 Correct 404 ms 97740 KB Output is correct
18 Correct 407 ms 97680 KB Output is correct
19 Correct 450 ms 103116 KB Output is correct
20 Correct 533 ms 102204 KB Output is correct
21 Correct 284 ms 98820 KB Output is correct
22 Correct 288 ms 98712 KB Output is correct
23 Correct 347 ms 98284 KB Output is correct
24 Correct 395 ms 98208 KB Output is correct
25 Correct 461 ms 104656 KB Output is correct
26 Correct 436 ms 95800 KB Output is correct
27 Correct 391 ms 95492 KB Output is correct
28 Correct 51 ms 31820 KB Output is correct
29 Correct 67 ms 34260 KB Output is correct
30 Correct 229 ms 34536 KB Output is correct
31 Correct 69 ms 34348 KB Output is correct
32 Correct 66 ms 34304 KB Output is correct
33 Correct 553 ms 34540 KB Output is correct
34 Correct 50 ms 31816 KB Output is correct
35 Execution timed out 3589 ms 90676 KB Time limit exceeded
36 Halted 0 ms 0 KB -