oj.uz

Submission #656235

# Submission time Handle Problem Language Result Execution time Memory
656235 2022-11-06T15:33:26 Z 600Mihnea Inside information (BOI21_servers) C++17
52.5 / 100
 3500 ms 114564 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]) {
      vector<int> vals;
      int cur = a;
      int guy = -1;
      while (curpar[cur]) {
        vals.push_back(when[cur]);
        guy = cur;
        cur = curpar[cur];
      }
      bool is_inc = 1;
      for (int it = 1; it < (int) vals.size(); it++) {
        is_inc &= (vals[it - 1] < vals[it]);
      }
      assert(is_inc == is);
      if (!is_inc) {
        continue;
      }
      assert(!vals.empty());
      assert(guy != -1);
      int last_value = vals.back();
      assert(last_value == send);
      assert(last_value == goval[guy]);
      if (last_value < T) {
        sol[T]++;
        for (auto &some : all) {
          if (goval[guy] < 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;
  if (home) {
     ///cout << "centroid = " << a << "\n";
  }

  {
    /// the case for a
    for (auto &T : cq[a]) {
      sol[T] += kekdfs(a, 0, -1, T);
    }
  }
  if (home) {
    ///cout << "done\n";
  }
  {
    /// 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);
    }
  }
  if (home) {
    ///cout << "really done\n";
  }

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

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31752 KB Output is correct
2 Correct 69 ms 34032 KB Output is correct
3 Correct 59 ms 34004 KB Output is correct
4 Correct 65 ms 34276 KB Output is correct
5 Correct 59 ms 34104 KB Output is correct
6 Correct 62 ms 33932 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31752 KB Output is correct
2 Correct 69 ms 34032 KB Output is correct
3 Correct 59 ms 34004 KB Output is correct
4 Correct 65 ms 34276 KB Output is correct
5 Correct 59 ms 34104 KB Output is correct
6 Correct 62 ms 33932 KB Output is correct
7 Correct 52 ms 31868 KB Output is correct
8 Correct 98 ms 34128 KB Output is correct
9 Correct 231 ms 34168 KB Output is correct
10 Correct 382 ms 34268 KB Output is correct
11 Correct 548 ms 34332 KB Output is correct
12 Correct 622 ms 34036 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31948 KB Output is correct
2 Correct 281 ms 99956 KB Output is correct
3 Correct 272 ms 99984 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31948 KB Output is correct
2 Correct 281 ms 99956 KB Output is correct
3 Correct 272 ms 99984 KB Output is correct
4 Correct 49 ms 31904 KB Output is correct
5 Execution timed out 3574 ms 90760 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 31760 KB Output is correct
2 Correct 349 ms 114308 KB Output is correct
3 Correct 340 ms 114124 KB Output is correct
4 Correct 282 ms 114564 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 31760 KB Output is correct
2 Correct 349 ms 114308 KB Output is correct
3 Correct 340 ms 114124 KB Output is correct
4 Correct 282 ms 114564 KB Output is correct
5 Correct 47 ms 31760 KB Output is correct
6 Execution timed out 3577 ms 105192 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31864 KB Output is correct
2 Correct 270 ms 97132 KB Output is correct
3 Correct 302 ms 96332 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31864 KB Output is correct
2 Correct 270 ms 97132 KB Output is correct
3 Correct 302 ms 96332 KB Output is correct
4 Correct 50 ms 31784 KB Output is correct
5 Execution timed out 3551 ms 88128 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 31852 KB Output is correct
2 Correct 343 ms 114188 KB Output is correct
3 Correct 335 ms 114252 KB Output is correct
4 Correct 284 ms 114480 KB Output is correct
5 Correct 48 ms 31792 KB Output is correct
6 Correct 267 ms 97108 KB Output is correct
7 Correct 297 ms 96196 KB Output is correct
8 Correct 398 ms 97808 KB Output is correct
9 Correct 410 ms 97704 KB Output is correct
10 Correct 467 ms 103244 KB Output is correct
11 Correct 502 ms 102028 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 31852 KB Output is correct
2 Correct 343 ms 114188 KB Output is correct
3 Correct 335 ms 114252 KB Output is correct
4 Correct 284 ms 114480 KB Output is correct
5 Correct 48 ms 31792 KB Output is correct
6 Correct 267 ms 97108 KB Output is correct
7 Correct 297 ms 96196 KB Output is correct
8 Correct 398 ms 97808 KB Output is correct
9 Correct 410 ms 97704 KB Output is correct
10 Correct 467 ms 103244 KB Output is correct
11 Correct 502 ms 102028 KB Output is correct
12 Correct 48 ms 31788 KB Output is correct
13 Execution timed out 3583 ms 105368 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31820 KB Output is correct
2 Correct 71 ms 34144 KB Output is correct
3 Correct 62 ms 33996 KB Output is correct
4 Correct 74 ms 34292 KB Output is correct
5 Correct 59 ms 34140 KB Output is correct
6 Correct 62 ms 33868 KB Output is correct
7 Correct 49 ms 31828 KB Output is correct
8 Correct 262 ms 99980 KB Output is correct
9 Correct 306 ms 99988 KB Output is correct
10 Correct 45 ms 31824 KB Output is correct
11 Correct 371 ms 114252 KB Output is correct
12 Correct 334 ms 114180 KB Output is correct
13 Correct 289 ms 114552 KB Output is correct
14 Correct 48 ms 31820 KB Output is correct
15 Correct 267 ms 97064 KB Output is correct
16 Correct 313 ms 96204 KB Output is correct
17 Correct 417 ms 97756 KB Output is correct
18 Correct 390 ms 97668 KB Output is correct
19 Correct 465 ms 103368 KB Output is correct
20 Correct 481 ms 102072 KB Output is correct
21 Correct 289 ms 98872 KB Output is correct
22 Correct 277 ms 98776 KB Output is correct
23 Correct 327 ms 98276 KB Output is correct
24 Correct 319 ms 98132 KB Output is correct
25 Correct 484 ms 106576 KB Output is correct
26 Correct 405 ms 95828 KB Output is correct
27 Correct 364 ms 95440 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31820 KB Output is correct
2 Correct 71 ms 34144 KB Output is correct
3 Correct 62 ms 33996 KB Output is correct
4 Correct 74 ms 34292 KB Output is correct
5 Correct 59 ms 34140 KB Output is correct
6 Correct 62 ms 33868 KB Output is correct
7 Correct 49 ms 31828 KB Output is correct
8 Correct 262 ms 99980 KB Output is correct
9 Correct 306 ms 99988 KB Output is correct
10 Correct 45 ms 31824 KB Output is correct
11 Correct 371 ms 114252 KB Output is correct
12 Correct 334 ms 114180 KB Output is correct
13 Correct 289 ms 114552 KB Output is correct
14 Correct 48 ms 31820 KB Output is correct
15 Correct 267 ms 97064 KB Output is correct
16 Correct 313 ms 96204 KB Output is correct
17 Correct 417 ms 97756 KB Output is correct
18 Correct 390 ms 97668 KB Output is correct
19 Correct 465 ms 103368 KB Output is correct
20 Correct 481 ms 102072 KB Output is correct
21 Correct 289 ms 98872 KB Output is correct
22 Correct 277 ms 98776 KB Output is correct
23 Correct 327 ms 98276 KB Output is correct
24 Correct 319 ms 98132 KB Output is correct
25 Correct 484 ms 106576 KB Output is correct
26 Correct 405 ms 95828 KB Output is correct
27 Correct 364 ms 95440 KB Output is correct
28 Correct 54 ms 31812 KB Output is correct
29 Correct 95 ms 34220 KB Output is correct
30 Correct 238 ms 34152 KB Output is correct
31 Correct 373 ms 34400 KB Output is correct
32 Correct 551 ms 34424 KB Output is correct
33 Correct 661 ms 34052 KB Output is correct
34 Correct 51 ms 31820 KB Output is correct
35 Execution timed out 3572 ms 90708 KB Time limit exceeded
36 Halted 0 ms 0 KB -