oj.uz

Submission #656234

# Submission time Handle Problem Language Result Execution time Memory
656234 2022-11-06T15:30:20 Z 600Mihnea Inside information (BOI21_servers) C++17
52.5 / 100
 3500 ms 114656 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 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 &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 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, 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

    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: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 dfsexplore(int, int, int)':
servers.cpp:210:23: warning: unused variable 'i' [-Wunused-variable]
  210 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp: In function 'void cdecomp(int)':
servers.cpp:304:23: warning: unused variable 'i' [-Wunused-variable]
  304 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp:257:7: warning: variable 'group' set but not used [-Wunused-but-set-variable]
  257 |   int group = 0;
      |       ^~~~~
servers.cpp: In function 'int main()':
servers.cpp:407:13: warning: unused variable 'INF' [-Wunused-variable]
  407 |   const int INF = (int)1e9 + 7;
      |             ^~~
servers.cpp:316:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  316 |     freopen("___input___.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 31800 KB Output is correct
2 Correct 118 ms 34068 KB Output is correct
3 Correct 81 ms 34008 KB Output is correct
4 Correct 117 ms 34284 KB Output is correct
5 Correct 60 ms 34080 KB Output is correct
6 Correct 68 ms 33868 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 31800 KB Output is correct
2 Correct 118 ms 34068 KB Output is correct
3 Correct 81 ms 34008 KB Output is correct
4 Correct 117 ms 34284 KB Output is correct
5 Correct 60 ms 34080 KB Output is correct
6 Correct 68 ms 33868 KB Output is correct
7 Correct 57 ms 31844 KB Output is correct
8 Correct 105 ms 34208 KB Output is correct
9 Correct 267 ms 34156 KB Output is correct
10 Correct 427 ms 34272 KB Output is correct
11 Correct 642 ms 34316 KB Output is correct
12 Correct 611 ms 34040 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31760 KB Output is correct
2 Correct 295 ms 99888 KB Output is correct
3 Correct 274 ms 99964 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31760 KB Output is correct
2 Correct 295 ms 99888 KB Output is correct
3 Correct 274 ms 99964 KB Output is correct
4 Correct 54 ms 31816 KB Output is correct
5 Execution timed out 3599 ms 90656 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 31868 KB Output is correct
2 Correct 394 ms 114208 KB Output is correct
3 Correct 357 ms 114104 KB Output is correct
4 Correct 278 ms 114556 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 31868 KB Output is correct
2 Correct 394 ms 114208 KB Output is correct
3 Correct 357 ms 114104 KB Output is correct
4 Correct 278 ms 114556 KB Output is correct
5 Correct 49 ms 31812 KB Output is correct
6 Execution timed out 3596 ms 105356 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 31856 KB Output is correct
2 Correct 271 ms 97312 KB Output is correct
3 Correct 355 ms 96164 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 31856 KB Output is correct
2 Correct 271 ms 97312 KB Output is correct
3 Correct 355 ms 96164 KB Output is correct
4 Correct 55 ms 31764 KB Output is correct
5 Execution timed out 3576 ms 88268 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 31816 KB Output is correct
2 Correct 355 ms 114224 KB Output is correct
3 Correct 330 ms 114152 KB Output is correct
4 Correct 288 ms 114528 KB Output is correct
5 Correct 48 ms 31820 KB Output is correct
6 Correct 276 ms 97084 KB Output is correct
7 Correct 304 ms 96212 KB Output is correct
8 Correct 468 ms 97768 KB Output is correct
9 Correct 406 ms 97672 KB Output is correct
10 Correct 463 ms 103140 KB Output is correct
11 Correct 480 ms 102076 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 31816 KB Output is correct
2 Correct 355 ms 114224 KB Output is correct
3 Correct 330 ms 114152 KB Output is correct
4 Correct 288 ms 114528 KB Output is correct
5 Correct 48 ms 31820 KB Output is correct
6 Correct 276 ms 97084 KB Output is correct
7 Correct 304 ms 96212 KB Output is correct
8 Correct 468 ms 97768 KB Output is correct
9 Correct 406 ms 97672 KB Output is correct
10 Correct 463 ms 103140 KB Output is correct
11 Correct 480 ms 102076 KB Output is correct
12 Correct 48 ms 31740 KB Output is correct
13 Execution timed out 3601 ms 105276 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 31804 KB Output is correct
2 Correct 66 ms 34220 KB Output is correct
3 Correct 68 ms 34064 KB Output is correct
4 Correct 67 ms 34188 KB Output is correct
5 Correct 59 ms 34128 KB Output is correct
6 Correct 60 ms 33924 KB Output is correct
7 Correct 48 ms 31948 KB Output is correct
8 Correct 272 ms 100060 KB Output is correct
9 Correct 277 ms 99988 KB Output is correct
10 Correct 57 ms 31772 KB Output is correct
11 Correct 342 ms 114136 KB Output is correct
12 Correct 339 ms 114136 KB Output is correct
13 Correct 283 ms 114656 KB Output is correct
14 Correct 48 ms 31748 KB Output is correct
15 Correct 262 ms 97144 KB Output is correct
16 Correct 360 ms 96224 KB Output is correct
17 Correct 472 ms 97776 KB Output is correct
18 Correct 385 ms 97888 KB Output is correct
19 Correct 498 ms 103144 KB Output is correct
20 Correct 516 ms 102092 KB Output is correct
21 Correct 288 ms 98808 KB Output is correct
22 Correct 274 ms 98740 KB Output is correct
23 Correct 329 ms 98180 KB Output is correct
24 Correct 332 ms 98156 KB Output is correct
25 Correct 489 ms 105524 KB Output is correct
26 Correct 375 ms 95788 KB Output is correct
27 Correct 401 ms 95488 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31804 KB Output is correct
2 Correct 66 ms 34220 KB Output is correct
3 Correct 68 ms 34064 KB Output is correct
4 Correct 67 ms 34188 KB Output is correct
5 Correct 59 ms 34128 KB Output is correct
6 Correct 60 ms 33924 KB Output is correct
7 Correct 48 ms 31948 KB Output is correct
8 Correct 272 ms 100060 KB Output is correct
9 Correct 277 ms 99988 KB Output is correct
10 Correct 57 ms 31772 KB Output is correct
11 Correct 342 ms 114136 KB Output is correct
12 Correct 339 ms 114136 KB Output is correct
13 Correct 283 ms 114656 KB Output is correct
14 Correct 48 ms 31748 KB Output is correct
15 Correct 262 ms 97144 KB Output is correct
16 Correct 360 ms 96224 KB Output is correct
17 Correct 472 ms 97776 KB Output is correct
18 Correct 385 ms 97888 KB Output is correct
19 Correct 498 ms 103144 KB Output is correct
20 Correct 516 ms 102092 KB Output is correct
21 Correct 288 ms 98808 KB Output is correct
22 Correct 274 ms 98740 KB Output is correct
23 Correct 329 ms 98180 KB Output is correct
24 Correct 332 ms 98156 KB Output is correct
25 Correct 489 ms 105524 KB Output is correct
26 Correct 375 ms 95788 KB Output is correct
27 Correct 401 ms 95488 KB Output is correct
28 Correct 50 ms 31820 KB Output is correct
29 Correct 101 ms 34164 KB Output is correct
30 Correct 247 ms 34280 KB Output is correct
31 Correct 398 ms 34272 KB Output is correct
32 Correct 567 ms 34400 KB Output is correct
33 Correct 587 ms 34044 KB Output is correct
34 Correct 48 ms 31820 KB Output is correct
35 Execution timed out 3605 ms 90692 KB Time limit exceeded
36 Halted 0 ms 0 KB -