oj.uz

Submission #656245

# Submission time Handle Problem Language Result Execution time Memory
656245 2022-11-06T15:51:05 Z 600Mihnea Inside information (BOI21_servers) C++17
67.5 / 100
 3500 ms 117464 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;

  {
    /// the case for a
    for (auto &T : cq[a]) {
      for (auto &lmao : all) {
        sol[T] += (lmao.finish < 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);
    }
  }
  sort(all.begin(), all.end(), [&] (T a, T b) {
    return a.finish < b.finish;
  });
  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:296:23: warning: unused variable 'i' [-Wunused-variable]
  296 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp: In function 'int main()':
servers.cpp:398:13: warning: unused variable 'INF' [-Wunused-variable]
  398 |   const int INF = (int)1e9 + 7;
      |             ^~~
servers.cpp:308:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  308 |     freopen("___input___.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31792 KB Output is correct
2 Correct 63 ms 34116 KB Output is correct
3 Correct 57 ms 33992 KB Output is correct
4 Correct 67 ms 34192 KB Output is correct
5 Correct 67 ms 34108 KB Output is correct
6 Correct 61 ms 33896 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31792 KB Output is correct
2 Correct 63 ms 34116 KB Output is correct
3 Correct 57 ms 33992 KB Output is correct
4 Correct 67 ms 34192 KB Output is correct
5 Correct 67 ms 34108 KB Output is correct
6 Correct 61 ms 33896 KB Output is correct
7 Correct 51 ms 32204 KB Output is correct
8 Correct 68 ms 34680 KB Output is correct
9 Correct 112 ms 35036 KB Output is correct
10 Correct 89 ms 34812 KB Output is correct
11 Correct 85 ms 34304 KB Output is correct
12 Correct 131 ms 34684 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31820 KB Output is correct
2 Correct 303 ms 100164 KB Output is correct
3 Correct 306 ms 99936 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31820 KB Output is correct
2 Correct 303 ms 100164 KB Output is correct
3 Correct 306 ms 99936 KB Output is correct
4 Correct 52 ms 32332 KB Output is correct
5 Correct 1140 ms 102212 KB Output is correct
6 Execution timed out 3563 ms 90712 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 31848 KB Output is correct
2 Correct 364 ms 114152 KB Output is correct
3 Correct 343 ms 114204 KB Output is correct
4 Correct 296 ms 114528 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 31848 KB Output is correct
2 Correct 364 ms 114152 KB Output is correct
3 Correct 343 ms 114204 KB Output is correct
4 Correct 296 ms 114528 KB Output is correct
5 Correct 46 ms 32268 KB Output is correct
6 Correct 377 ms 117108 KB Output is correct
7 Correct 726 ms 117464 KB Output is correct
8 Correct 392 ms 116960 KB Output is correct
9 Correct 363 ms 116948 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 31744 KB Output is correct
2 Correct 283 ms 97184 KB Output is correct
3 Correct 316 ms 96292 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 31744 KB Output is correct
2 Correct 283 ms 97184 KB Output is correct
3 Correct 316 ms 96292 KB Output is correct
4 Correct 53 ms 32248 KB Output is correct
5 Correct 315 ms 100336 KB Output is correct
6 Correct 308 ms 99064 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 31820 KB Output is correct
2 Correct 336 ms 114184 KB Output is correct
3 Correct 334 ms 114252 KB Output is correct
4 Correct 295 ms 114548 KB Output is correct
5 Correct 49 ms 31820 KB Output is correct
6 Correct 306 ms 97256 KB Output is correct
7 Correct 329 ms 96252 KB Output is correct
8 Correct 406 ms 97816 KB Output is correct
9 Correct 411 ms 97656 KB Output is correct
10 Correct 559 ms 103172 KB Output is correct
11 Correct 479 ms 102096 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 31820 KB Output is correct
2 Correct 336 ms 114184 KB Output is correct
3 Correct 334 ms 114252 KB Output is correct
4 Correct 295 ms 114548 KB Output is correct
5 Correct 49 ms 31820 KB Output is correct
6 Correct 306 ms 97256 KB Output is correct
7 Correct 329 ms 96252 KB Output is correct
8 Correct 406 ms 97816 KB Output is correct
9 Correct 411 ms 97656 KB Output is correct
10 Correct 559 ms 103172 KB Output is correct
11 Correct 479 ms 102096 KB Output is correct
12 Correct 46 ms 32172 KB Output is correct
13 Correct 356 ms 117120 KB Output is correct
14 Correct 683 ms 117448 KB Output is correct
15 Correct 354 ms 116848 KB Output is correct
16 Correct 352 ms 116956 KB Output is correct
17 Correct 50 ms 32156 KB Output is correct
18 Correct 311 ms 100156 KB Output is correct
19 Correct 331 ms 99020 KB Output is correct
20 Correct 414 ms 100272 KB Output is correct
21 Correct 417 ms 100660 KB Output is correct
22 Correct 1269 ms 104968 KB Output is correct
23 Execution timed out 3596 ms 106100 KB Time limit exceeded
24 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 65 ms 34136 KB Output is correct
3 Correct 58 ms 34000 KB Output is correct
4 Correct 68 ms 34292 KB Output is correct
5 Correct 63 ms 34228 KB Output is correct
6 Correct 60 ms 33956 KB Output is correct
7 Correct 49 ms 31884 KB Output is correct
8 Correct 261 ms 99964 KB Output is correct
9 Correct 281 ms 100036 KB Output is correct
10 Correct 46 ms 31840 KB Output is correct
11 Correct 336 ms 114124 KB Output is correct
12 Correct 358 ms 114268 KB Output is correct
13 Correct 292 ms 114616 KB Output is correct
14 Correct 48 ms 31756 KB Output is correct
15 Correct 295 ms 97188 KB Output is correct
16 Correct 294 ms 96368 KB Output is correct
17 Correct 407 ms 97708 KB Output is correct
18 Correct 399 ms 97744 KB Output is correct
19 Correct 513 ms 103212 KB Output is correct
20 Correct 532 ms 102108 KB Output is correct
21 Correct 319 ms 98740 KB Output is correct
22 Correct 297 ms 98748 KB Output is correct
23 Correct 338 ms 98252 KB Output is correct
24 Correct 361 ms 98208 KB Output is correct
25 Correct 474 ms 104636 KB Output is correct
26 Correct 397 ms 95740 KB Output is correct
27 Correct 373 ms 95616 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 65 ms 34136 KB Output is correct
3 Correct 58 ms 34000 KB Output is correct
4 Correct 68 ms 34292 KB Output is correct
5 Correct 63 ms 34228 KB Output is correct
6 Correct 60 ms 33956 KB Output is correct
7 Correct 49 ms 31884 KB Output is correct
8 Correct 261 ms 99964 KB Output is correct
9 Correct 281 ms 100036 KB Output is correct
10 Correct 46 ms 31840 KB Output is correct
11 Correct 336 ms 114124 KB Output is correct
12 Correct 358 ms 114268 KB Output is correct
13 Correct 292 ms 114616 KB Output is correct
14 Correct 48 ms 31756 KB Output is correct
15 Correct 295 ms 97188 KB Output is correct
16 Correct 294 ms 96368 KB Output is correct
17 Correct 407 ms 97708 KB Output is correct
18 Correct 399 ms 97744 KB Output is correct
19 Correct 513 ms 103212 KB Output is correct
20 Correct 532 ms 102108 KB Output is correct
21 Correct 319 ms 98740 KB Output is correct
22 Correct 297 ms 98748 KB Output is correct
23 Correct 338 ms 98252 KB Output is correct
24 Correct 361 ms 98208 KB Output is correct
25 Correct 474 ms 104636 KB Output is correct
26 Correct 397 ms 95740 KB Output is correct
27 Correct 373 ms 95616 KB Output is correct
28 Correct 51 ms 32204 KB Output is correct
29 Correct 74 ms 34708 KB Output is correct
30 Correct 114 ms 35048 KB Output is correct
31 Correct 71 ms 34892 KB Output is correct
32 Correct 62 ms 34340 KB Output is correct
33 Correct 126 ms 34756 KB Output is correct
34 Correct 50 ms 32332 KB Output is correct
35 Correct 1048 ms 102284 KB Output is correct
36 Execution timed out 3556 ms 90836 KB Time limit exceeded
37 Halted 0 ms 0 KB -