oj.uz

Submission #656244

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


    }
  }
}

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

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 31752 KB Output is correct
2 Correct 73 ms 34104 KB Output is correct
3 Correct 65 ms 34020 KB Output is correct
4 Correct 80 ms 34220 KB Output is correct
5 Correct 62 ms 34108 KB Output is correct
6 Correct 64 ms 33944 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 31752 KB Output is correct
2 Correct 73 ms 34104 KB Output is correct
3 Correct 65 ms 34020 KB Output is correct
4 Correct 80 ms 34220 KB Output is correct
5 Correct 62 ms 34108 KB Output is correct
6 Correct 64 ms 33944 KB Output is correct
7 Correct 52 ms 32300 KB Output is correct
8 Correct 73 ms 34696 KB Output is correct
9 Correct 252 ms 34924 KB Output is correct
10 Correct 71 ms 34856 KB Output is correct
11 Correct 66 ms 34404 KB Output is correct
12 Correct 239 ms 34760 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 31884 KB Output is correct
2 Correct 278 ms 99980 KB Output is correct
3 Correct 275 ms 99896 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 31884 KB Output is correct
2 Correct 278 ms 99980 KB Output is correct
3 Correct 275 ms 99896 KB Output is correct
4 Correct 52 ms 32268 KB Output is correct
5 Execution timed out 3576 ms 90612 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 31868 KB Output is correct
2 Correct 348 ms 114152 KB Output is correct
3 Correct 350 ms 114196 KB Output is correct
4 Correct 292 ms 114564 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 31868 KB Output is correct
2 Correct 348 ms 114152 KB Output is correct
3 Correct 350 ms 114196 KB Output is correct
4 Correct 292 ms 114564 KB Output is correct
5 Correct 46 ms 32204 KB Output is correct
6 Correct 378 ms 117160 KB Output is correct
7 Correct 705 ms 117596 KB Output is correct
8 Correct 365 ms 116880 KB Output is correct
9 Correct 357 ms 116908 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31820 KB Output is correct
2 Correct 285 ms 97216 KB Output is correct
3 Correct 348 ms 96324 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 31820 KB Output is correct
2 Correct 285 ms 97216 KB Output is correct
3 Correct 348 ms 96324 KB Output is correct
4 Correct 53 ms 32272 KB Output is correct
5 Correct 320 ms 100140 KB Output is correct
6 Correct 317 ms 99036 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 31776 KB Output is correct
2 Correct 338 ms 114124 KB Output is correct
3 Correct 336 ms 114240 KB Output is correct
4 Correct 289 ms 114512 KB Output is correct
5 Correct 49 ms 31744 KB Output is correct
6 Correct 302 ms 97068 KB Output is correct
7 Correct 298 ms 96272 KB Output is correct
8 Correct 421 ms 97736 KB Output is correct
9 Correct 393 ms 97740 KB Output is correct
10 Correct 453 ms 103156 KB Output is correct
11 Correct 469 ms 102172 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 31776 KB Output is correct
2 Correct 338 ms 114124 KB Output is correct
3 Correct 336 ms 114240 KB Output is correct
4 Correct 289 ms 114512 KB Output is correct
5 Correct 49 ms 31744 KB Output is correct
6 Correct 302 ms 97068 KB Output is correct
7 Correct 298 ms 96272 KB Output is correct
8 Correct 421 ms 97736 KB Output is correct
9 Correct 393 ms 97740 KB Output is correct
10 Correct 453 ms 103156 KB Output is correct
11 Correct 469 ms 102172 KB Output is correct
12 Correct 46 ms 32188 KB Output is correct
13 Correct 361 ms 117108 KB Output is correct
14 Correct 688 ms 117536 KB Output is correct
15 Correct 361 ms 116940 KB Output is correct
16 Correct 356 ms 116928 KB Output is correct
17 Correct 50 ms 32204 KB Output is correct
18 Correct 315 ms 100264 KB Output is correct
19 Correct 313 ms 99036 KB Output is correct
20 Correct 486 ms 100132 KB Output is correct
21 Correct 417 ms 100720 KB Output is correct
22 Correct 1285 ms 104900 KB Output is correct
23 Execution timed out 3568 ms 106132 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 31820 KB Output is correct
2 Correct 77 ms 34012 KB Output is correct
3 Correct 64 ms 33996 KB Output is correct
4 Correct 74 ms 34176 KB Output is correct
5 Correct 69 ms 34124 KB Output is correct
6 Correct 68 ms 33936 KB Output is correct
7 Correct 54 ms 31848 KB Output is correct
8 Correct 354 ms 99972 KB Output is correct
9 Correct 267 ms 99988 KB Output is correct
10 Correct 46 ms 31828 KB Output is correct
11 Correct 349 ms 114284 KB Output is correct
12 Correct 349 ms 114212 KB Output is correct
13 Correct 284 ms 114528 KB Output is correct
14 Correct 48 ms 31756 KB Output is correct
15 Correct 292 ms 97296 KB Output is correct
16 Correct 299 ms 96248 KB Output is correct
17 Correct 392 ms 97700 KB Output is correct
18 Correct 383 ms 97704 KB Output is correct
19 Correct 479 ms 103228 KB Output is correct
20 Correct 487 ms 102084 KB Output is correct
21 Correct 299 ms 98832 KB Output is correct
22 Correct 296 ms 98836 KB Output is correct
23 Correct 329 ms 98104 KB Output is correct
24 Correct 319 ms 98232 KB Output is correct
25 Correct 476 ms 104584 KB Output is correct
26 Correct 391 ms 95816 KB Output is correct
27 Correct 393 ms 95440 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 31820 KB Output is correct
2 Correct 77 ms 34012 KB Output is correct
3 Correct 64 ms 33996 KB Output is correct
4 Correct 74 ms 34176 KB Output is correct
5 Correct 69 ms 34124 KB Output is correct
6 Correct 68 ms 33936 KB Output is correct
7 Correct 54 ms 31848 KB Output is correct
8 Correct 354 ms 99972 KB Output is correct
9 Correct 267 ms 99988 KB Output is correct
10 Correct 46 ms 31828 KB Output is correct
11 Correct 349 ms 114284 KB Output is correct
12 Correct 349 ms 114212 KB Output is correct
13 Correct 284 ms 114528 KB Output is correct
14 Correct 48 ms 31756 KB Output is correct
15 Correct 292 ms 97296 KB Output is correct
16 Correct 299 ms 96248 KB Output is correct
17 Correct 392 ms 97700 KB Output is correct
18 Correct 383 ms 97704 KB Output is correct
19 Correct 479 ms 103228 KB Output is correct
20 Correct 487 ms 102084 KB Output is correct
21 Correct 299 ms 98832 KB Output is correct
22 Correct 296 ms 98836 KB Output is correct
23 Correct 329 ms 98104 KB Output is correct
24 Correct 319 ms 98232 KB Output is correct
25 Correct 476 ms 104584 KB Output is correct
26 Correct 391 ms 95816 KB Output is correct
27 Correct 393 ms 95440 KB Output is correct
28 Correct 51 ms 32240 KB Output is correct
29 Correct 69 ms 34760 KB Output is correct
30 Correct 194 ms 34928 KB Output is correct
31 Correct 71 ms 34764 KB Output is correct
32 Correct 64 ms 34336 KB Output is correct
33 Correct 307 ms 34736 KB Output is correct
34 Correct 50 ms 32248 KB Output is correct
35 Execution timed out 3582 ms 90636 KB Time limit exceeded
36 Halted 0 ms 0 KB -