oj.uz

Submission #656247

# Submission time Handle Problem Language Result Execution time Memory
656247 2022-11-06T15:52:00 Z 600Mihnea Inside information (BOI21_servers) C++17
70 / 100
 3500 ms 120468 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);
  }
}


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});
    }
  }
}

int aib[N];

void add(int i, int x) {
  i++;
  while (i < N) {
    aib[i] += x;
    i += i & (-i);
  }
}

int gt(int i) {
  i++;
  int sol = 0;
  while (i) {
    sol += aib[i];
    i -= i & (-i);
  }
  return sol;
}

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;
  sort(all.begin(), all.end(), [&] (T a, T b) {
    return a.finish < b.finish;
  });
  {
    int ptr = 0;
    /// the case for a
    for (auto &T : cq[a]) {
      while (ptr < (int) all.size() && all[ptr].finish < T) {
        ptr++;
      }
      sol[T] += ptr;
    }
  }

  {
    /// 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(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) {
      add(all[ptr].start, +1);
      ptr++;
    }
    sol[T] += ptr;
    sol[T] -= gt(send);
  }
  for (int j = 0; j < ptr; j++) {
    add(all[j].start, -1);
  }
  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:298:23: warning: unused variable 'i' [-Wunused-variable]
  298 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp: In function 'int main()':
servers.cpp:400:13: warning: unused variable 'INF' [-Wunused-variable]
  400 |   const int INF = (int)1e9 + 7;
      |             ^~~
servers.cpp:310:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  310 |     freopen("___input___.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31812 KB Output is correct
2 Correct 66 ms 34040 KB Output is correct
3 Correct 58 ms 34012 KB Output is correct
4 Correct 67 ms 34248 KB Output is correct
5 Correct 62 ms 34092 KB Output is correct
6 Correct 61 ms 33868 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31812 KB Output is correct
2 Correct 66 ms 34040 KB Output is correct
3 Correct 58 ms 34012 KB Output is correct
4 Correct 67 ms 34248 KB Output is correct
5 Correct 62 ms 34092 KB Output is correct
6 Correct 61 ms 33868 KB Output is correct
7 Correct 49 ms 32232 KB Output is correct
8 Correct 66 ms 34748 KB Output is correct
9 Correct 61 ms 35000 KB Output is correct
10 Correct 71 ms 34764 KB Output is correct
11 Correct 67 ms 34288 KB Output is correct
12 Correct 59 ms 34740 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31844 KB Output is correct
2 Correct 271 ms 99980 KB Output is correct
3 Correct 273 ms 99948 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31844 KB Output is correct
2 Correct 271 ms 99980 KB Output is correct
3 Correct 273 ms 99948 KB Output is correct
4 Correct 55 ms 32244 KB Output is correct
5 Correct 277 ms 102168 KB Output is correct
6 Correct 212 ms 99932 KB Output is correct
7 Correct 232 ms 103316 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31856 KB Output is correct
2 Correct 340 ms 114188 KB Output is correct
3 Correct 333 ms 114332 KB Output is correct
4 Correct 324 ms 114636 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31856 KB Output is correct
2 Correct 340 ms 114188 KB Output is correct
3 Correct 333 ms 114332 KB Output is correct
4 Correct 324 ms 114636 KB Output is correct
5 Correct 54 ms 32256 KB Output is correct
6 Correct 365 ms 117040 KB Output is correct
7 Correct 711 ms 117500 KB Output is correct
8 Correct 374 ms 116916 KB Output is correct
9 Correct 403 ms 116860 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 31764 KB Output is correct
2 Correct 320 ms 97172 KB Output is correct
3 Correct 383 ms 96192 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 31764 KB Output is correct
2 Correct 320 ms 97172 KB Output is correct
3 Correct 383 ms 96192 KB Output is correct
4 Correct 52 ms 32184 KB Output is correct
5 Correct 406 ms 100208 KB Output is correct
6 Correct 306 ms 99040 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 31860 KB Output is correct
2 Correct 348 ms 114124 KB Output is correct
3 Correct 338 ms 114124 KB Output is correct
4 Correct 302 ms 114508 KB Output is correct
5 Correct 49 ms 31752 KB Output is correct
6 Correct 288 ms 97224 KB Output is correct
7 Correct 306 ms 96236 KB Output is correct
8 Correct 406 ms 97800 KB Output is correct
9 Correct 386 ms 97728 KB Output is correct
10 Correct 469 ms 103268 KB Output is correct
11 Correct 471 ms 102036 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 31860 KB Output is correct
2 Correct 348 ms 114124 KB Output is correct
3 Correct 338 ms 114124 KB Output is correct
4 Correct 302 ms 114508 KB Output is correct
5 Correct 49 ms 31752 KB Output is correct
6 Correct 288 ms 97224 KB Output is correct
7 Correct 306 ms 96236 KB Output is correct
8 Correct 406 ms 97800 KB Output is correct
9 Correct 386 ms 97728 KB Output is correct
10 Correct 469 ms 103268 KB Output is correct
11 Correct 471 ms 102036 KB Output is correct
12 Correct 49 ms 32180 KB Output is correct
13 Correct 358 ms 117112 KB Output is correct
14 Correct 687 ms 117600 KB Output is correct
15 Correct 349 ms 116940 KB Output is correct
16 Correct 356 ms 116996 KB Output is correct
17 Correct 50 ms 32164 KB Output is correct
18 Correct 320 ms 100144 KB Output is correct
19 Correct 320 ms 99020 KB Output is correct
20 Correct 417 ms 100148 KB Output is correct
21 Correct 422 ms 100728 KB Output is correct
22 Correct 1267 ms 104964 KB Output is correct
23 Execution timed out 3573 ms 106152 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31820 KB Output is correct
2 Correct 89 ms 34124 KB Output is correct
3 Correct 59 ms 34072 KB Output is correct
4 Correct 67 ms 34192 KB Output is correct
5 Correct 61 ms 34120 KB Output is correct
6 Correct 60 ms 33968 KB Output is correct
7 Correct 49 ms 31820 KB Output is correct
8 Correct 269 ms 100048 KB Output is correct
9 Correct 268 ms 99996 KB Output is correct
10 Correct 57 ms 31804 KB Output is correct
11 Correct 340 ms 114116 KB Output is correct
12 Correct 367 ms 114212 KB Output is correct
13 Correct 295 ms 114588 KB Output is correct
14 Correct 47 ms 31836 KB Output is correct
15 Correct 286 ms 97280 KB Output is correct
16 Correct 293 ms 96340 KB Output is correct
17 Correct 389 ms 97740 KB Output is correct
18 Correct 380 ms 97740 KB Output is correct
19 Correct 454 ms 103244 KB Output is correct
20 Correct 464 ms 102112 KB Output is correct
21 Correct 295 ms 98824 KB Output is correct
22 Correct 284 ms 98700 KB Output is correct
23 Correct 330 ms 98236 KB Output is correct
24 Correct 325 ms 98212 KB Output is correct
25 Correct 497 ms 104640 KB Output is correct
26 Correct 414 ms 95804 KB Output is correct
27 Correct 424 ms 95508 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31820 KB Output is correct
2 Correct 89 ms 34124 KB Output is correct
3 Correct 59 ms 34072 KB Output is correct
4 Correct 67 ms 34192 KB Output is correct
5 Correct 61 ms 34120 KB Output is correct
6 Correct 60 ms 33968 KB Output is correct
7 Correct 49 ms 31820 KB Output is correct
8 Correct 269 ms 100048 KB Output is correct
9 Correct 268 ms 99996 KB Output is correct
10 Correct 57 ms 31804 KB Output is correct
11 Correct 340 ms 114116 KB Output is correct
12 Correct 367 ms 114212 KB Output is correct
13 Correct 295 ms 114588 KB Output is correct
14 Correct 47 ms 31836 KB Output is correct
15 Correct 286 ms 97280 KB Output is correct
16 Correct 293 ms 96340 KB Output is correct
17 Correct 389 ms 97740 KB Output is correct
18 Correct 380 ms 97740 KB Output is correct
19 Correct 454 ms 103244 KB Output is correct
20 Correct 464 ms 102112 KB Output is correct
21 Correct 295 ms 98824 KB Output is correct
22 Correct 284 ms 98700 KB Output is correct
23 Correct 330 ms 98236 KB Output is correct
24 Correct 325 ms 98212 KB Output is correct
25 Correct 497 ms 104640 KB Output is correct
26 Correct 414 ms 95804 KB Output is correct
27 Correct 424 ms 95508 KB Output is correct
28 Correct 50 ms 32292 KB Output is correct
29 Correct 68 ms 34704 KB Output is correct
30 Correct 64 ms 34944 KB Output is correct
31 Correct 71 ms 34816 KB Output is correct
32 Correct 63 ms 34364 KB Output is correct
33 Correct 63 ms 34764 KB Output is correct
34 Correct 51 ms 32332 KB Output is correct
35 Correct 265 ms 102188 KB Output is correct
36 Correct 237 ms 99860 KB Output is correct
37 Correct 222 ms 103136 KB Output is correct
38 Correct 47 ms 33056 KB Output is correct
39 Correct 376 ms 120124 KB Output is correct
40 Correct 685 ms 120468 KB Output is correct
41 Correct 358 ms 119584 KB Output is correct
42 Correct 366 ms 119684 KB Output is correct
43 Correct 49 ms 33104 KB Output is correct
44 Correct 327 ms 103144 KB Output is correct
45 Correct 311 ms 101964 KB Output is correct
46 Correct 413 ms 103004 KB Output is correct
47 Correct 417 ms 103756 KB Output is correct
48 Correct 1331 ms 107616 KB Output is correct
49 Execution timed out 3581 ms 109072 KB Time limit exceeded
50 Halted 0 ms 0 KB -