oj.uz

Submission #656230

# Submission time Handle Problem Language Result Execution time Memory
656230 2022-11-06T15:20:22 Z 600Mihnea Inside information (BOI21_servers) C++17
52.5 / 100
 3500 ms 114596 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 inc;
};

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) {
  curpar[a] = p;
  for (auto &it : realg[a]) {
    int b = it.first, i = it.second;
    if (blocked[b] || b == p) {
      continue;
    }
    when[b] = i;
    dfsfromcen(b, a, group);
  }
}

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 group) {
  for (auto &it : realg[a]) {
    int b = it.first, i = it.second;
    if (blocked[b] || b == p) {
      continue;
    }
    dfsexplore(b, a, group);
  }
  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]);
      }
      if (!is_inc) {
        continue;
      }
      assert(!vals.empty());
      assert(guy != -1);
      int last_value = vals.back();
      assert(last_value == goval[guy]);
      if (last_value < T) {
        sol[T]++;
        for (auto &oth_guy : guys) {
          if (goval[guy] < goval[oth_guy]) {
            if (goval[oth_guy] < T) {
              sol[T]++;
            }
            assert(curpar[guy] == curpar[oth_guy]);
            assert(curpar[curpar[guy]] == 0);
            sol[T] += kekdfs(oth_guy, curpar[guy], goval[oth_guy], T);
          }
        }
      }
    }
  }
}

void cdecomp(int a) {
  compute_score(a);
  total_score = score[a];
  a = fndcen(a);

  guys.clear();
  int group = 0;
  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);
  }
  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

    group = 0;
    for (auto &it : realg[a]) {
      int b = it.first, i = it.second;
      if (blocked[b]) {
        continue;
      }
      dfsexplore(b, a, 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:134:23: warning: unused variable 'i' [-Wunused-variable]
  134 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp: In function 'int fndcen(int, int)':
servers.cpp:146:23: warning: unused variable 'i' [-Wunused-variable]
  146 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp:156:23: warning: unused variable 'i' [-Wunused-variable]
  156 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp: In function 'void dfsexplore(int, int, int)':
servers.cpp:200:23: warning: unused variable 'i' [-Wunused-variable]
  200 |     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:251:7: warning: variable 'group' set but not used [-Wunused-but-set-variable]
  251 |   int group = 0;
      |       ^~~~~
servers.cpp: In function 'int main()':
servers.cpp:401:13: warning: unused variable 'INF' [-Wunused-variable]
  401 |   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 47 ms 31820 KB Output is correct
2 Correct 63 ms 34056 KB Output is correct
3 Correct 59 ms 34036 KB Output is correct
4 Correct 66 ms 34164 KB Output is correct
5 Correct 58 ms 34172 KB Output is correct
6 Correct 58 ms 33832 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 63 ms 34056 KB Output is correct
3 Correct 59 ms 34036 KB Output is correct
4 Correct 66 ms 34164 KB Output is correct
5 Correct 58 ms 34172 KB Output is correct
6 Correct 58 ms 33832 KB Output is correct
7 Correct 51 ms 31752 KB Output is correct
8 Correct 95 ms 34220 KB Output is correct
9 Correct 303 ms 34148 KB Output is correct
10 Correct 373 ms 34380 KB Output is correct
11 Correct 553 ms 34260 KB Output is correct
12 Correct 1472 ms 34012 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 31868 KB Output is correct
2 Correct 261 ms 98644 KB Output is correct
3 Correct 263 ms 98580 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 31868 KB Output is correct
2 Correct 261 ms 98644 KB Output is correct
3 Correct 263 ms 98580 KB Output is correct
4 Correct 49 ms 31796 KB Output is correct
5 Execution timed out 3575 ms 89356 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31748 KB Output is correct
2 Correct 352 ms 114172 KB Output is correct
3 Correct 370 ms 114320 KB Output is correct
4 Correct 314 ms 114596 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31748 KB Output is correct
2 Correct 352 ms 114172 KB Output is correct
3 Correct 370 ms 114320 KB Output is correct
4 Correct 314 ms 114596 KB Output is correct
5 Correct 50 ms 31820 KB Output is correct
6 Execution timed out 3560 ms 105312 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 31752 KB Output is correct
2 Correct 261 ms 96596 KB Output is correct
3 Correct 309 ms 96272 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31752 KB Output is correct
2 Correct 261 ms 96596 KB Output is correct
3 Correct 309 ms 96272 KB Output is correct
4 Correct 52 ms 31748 KB Output is correct
5 Execution timed out 3570 ms 87516 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31828 KB Output is correct
2 Correct 333 ms 114212 KB Output is correct
3 Correct 337 ms 114116 KB Output is correct
4 Correct 268 ms 114468 KB Output is correct
5 Correct 48 ms 31820 KB Output is correct
6 Correct 253 ms 96496 KB Output is correct
7 Correct 288 ms 96248 KB Output is correct
8 Correct 386 ms 97808 KB Output is correct
9 Correct 375 ms 97684 KB Output is correct
10 Correct 446 ms 103180 KB Output is correct
11 Correct 463 ms 102168 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31828 KB Output is correct
2 Correct 333 ms 114212 KB Output is correct
3 Correct 337 ms 114116 KB Output is correct
4 Correct 268 ms 114468 KB Output is correct
5 Correct 48 ms 31820 KB Output is correct
6 Correct 253 ms 96496 KB Output is correct
7 Correct 288 ms 96248 KB Output is correct
8 Correct 386 ms 97808 KB Output is correct
9 Correct 375 ms 97684 KB Output is correct
10 Correct 446 ms 103180 KB Output is correct
11 Correct 463 ms 102168 KB Output is correct
12 Correct 50 ms 31820 KB Output is correct
13 Execution timed out 3572 ms 105248 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31824 KB Output is correct
2 Correct 64 ms 34104 KB Output is correct
3 Correct 59 ms 34092 KB Output is correct
4 Correct 70 ms 34252 KB Output is correct
5 Correct 61 ms 34124 KB Output is correct
6 Correct 63 ms 33856 KB Output is correct
7 Correct 49 ms 31816 KB Output is correct
8 Correct 285 ms 98632 KB Output is correct
9 Correct 271 ms 98572 KB Output is correct
10 Correct 46 ms 31764 KB Output is correct
11 Correct 355 ms 114096 KB Output is correct
12 Correct 355 ms 114184 KB Output is correct
13 Correct 307 ms 114552 KB Output is correct
14 Correct 49 ms 31820 KB Output is correct
15 Correct 262 ms 96592 KB Output is correct
16 Correct 368 ms 96184 KB Output is correct
17 Correct 395 ms 97808 KB Output is correct
18 Correct 390 ms 97684 KB Output is correct
19 Correct 447 ms 103136 KB Output is correct
20 Correct 496 ms 102108 KB Output is correct
21 Correct 283 ms 98188 KB Output is correct
22 Correct 290 ms 98164 KB Output is correct
23 Correct 325 ms 98152 KB Output is correct
24 Correct 319 ms 98168 KB Output is correct
25 Correct 463 ms 106096 KB Output is correct
26 Correct 386 ms 95912 KB Output is correct
27 Correct 357 ms 95564 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31824 KB Output is correct
2 Correct 64 ms 34104 KB Output is correct
3 Correct 59 ms 34092 KB Output is correct
4 Correct 70 ms 34252 KB Output is correct
5 Correct 61 ms 34124 KB Output is correct
6 Correct 63 ms 33856 KB Output is correct
7 Correct 49 ms 31816 KB Output is correct
8 Correct 285 ms 98632 KB Output is correct
9 Correct 271 ms 98572 KB Output is correct
10 Correct 46 ms 31764 KB Output is correct
11 Correct 355 ms 114096 KB Output is correct
12 Correct 355 ms 114184 KB Output is correct
13 Correct 307 ms 114552 KB Output is correct
14 Correct 49 ms 31820 KB Output is correct
15 Correct 262 ms 96592 KB Output is correct
16 Correct 368 ms 96184 KB Output is correct
17 Correct 395 ms 97808 KB Output is correct
18 Correct 390 ms 97684 KB Output is correct
19 Correct 447 ms 103136 KB Output is correct
20 Correct 496 ms 102108 KB Output is correct
21 Correct 283 ms 98188 KB Output is correct
22 Correct 290 ms 98164 KB Output is correct
23 Correct 325 ms 98152 KB Output is correct
24 Correct 319 ms 98168 KB Output is correct
25 Correct 463 ms 106096 KB Output is correct
26 Correct 386 ms 95912 KB Output is correct
27 Correct 357 ms 95564 KB Output is correct
28 Correct 55 ms 31840 KB Output is correct
29 Correct 98 ms 34140 KB Output is correct
30 Correct 292 ms 34196 KB Output is correct
31 Correct 386 ms 34260 KB Output is correct
32 Correct 579 ms 34240 KB Output is correct
33 Correct 1270 ms 34016 KB Output is correct
34 Correct 50 ms 31820 KB Output is correct
35 Execution timed out 3572 ms 89276 KB Time limit exceeded
36 Halted 0 ms 0 KB -