oj.uz

Submission #656229

# Submission time Handle Problem Language Result Execution time Memory
656229 2022-11-06T15:17:14 Z 600Mihnea Inside information (BOI21_servers) C++17
52.5 / 100
 3500 ms 114676 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];
int print[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];

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) {
    ///cout << a << " : " << p << "\n";
    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];
      }
      /// vals should be increasing
      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) {
        print[T]++;
        for (auto &oth_guy : guys) {
          if (oth_guy != guy && goval[guy] < goval[oth_guy]) {
            if (goval[oth_guy] < T) {
              print[T]++;
            }
            assert(curpar[guy] == curpar[oth_guy]);
            assert(curpar[curpar[guy]] == 0);
            print[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]) {
      print[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;
  int ciq = 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 (q1[i]) {
      ciq++;
      assert(tp[i] == 3);
      int vertex = q1[i];
      int ret = 1;

      for (auto& it : gg[vertex]) {
        int v2 = it.first;
        ret += cnt[v2];
      }

      int cnt_down = min(dcr[q1[i]], dep[q1[i]]);
      int down = 0;

      for (int j = 1; j <= cnt_down; j++) {
        ret += (idup[vertex] < i);
        for (auto& it : gg[p[vertex]]) {
          int v2 = it.first;
          if (idup[vertex] < idup[v2]) {
            ret += cnt[v2];
          }
        }
        vertex = p[vertex];
      }
      sol[i] = ret;
    }
  }
  if (cnt3) {
    assert(cnt_2 == n - 1);
  }
  /**unsigned long long h = 0;
  for (int i = 1; i <= n + k - 1; i++) h = 7777 * h + sol[i];
  if (home) {
    assert(h == 8758581888253777949);
    cout << "good\n";
    exit(0);
  }**/
  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 << print[i] + 1 << "\n";
    }
  }

  return 0;
}

Compilation message

servers.cpp: In function 'void compute_score(int, int)':
servers.cpp:131:23: warning: unused variable 'i' [-Wunused-variable]
  131 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp: In function 'int fndcen(int, int)':
servers.cpp:143:23: warning: unused variable 'i' [-Wunused-variable]
  143 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp:153:23: warning: unused variable 'i' [-Wunused-variable]
  153 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp: In function 'void dfsexplore(int, int, int)':
servers.cpp:197:23: warning: unused variable 'i' [-Wunused-variable]
  197 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp: In function 'void cdecomp(int)':
servers.cpp:297:23: warning: unused variable 'i' [-Wunused-variable]
  297 |     int b = it.first, i = it.second;
      |                       ^
servers.cpp:250:7: warning: variable 'group' set but not used [-Wunused-but-set-variable]
  250 |   int group = 0;
      |       ^~~~~
servers.cpp: In function 'int main()':
servers.cpp:427:11: warning: unused variable 'down' [-Wunused-variable]
  427 |       int down = 0;
      |           ^~~~
servers.cpp:400:13: warning: unused variable 'INF' [-Wunused-variable]
  400 |   const int INF = (int)1e9 + 7;
      |             ^~~
servers.cpp:309:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  309 |     freopen("___input___.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 31876 KB Output is correct
2 Correct 63 ms 34096 KB Output is correct
3 Correct 60 ms 34088 KB Output is correct
4 Correct 69 ms 34176 KB Output is correct
5 Correct 68 ms 34284 KB Output is correct
6 Correct 62 ms 33924 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 31876 KB Output is correct
2 Correct 63 ms 34096 KB Output is correct
3 Correct 60 ms 34088 KB Output is correct
4 Correct 69 ms 34176 KB Output is correct
5 Correct 68 ms 34284 KB Output is correct
6 Correct 62 ms 33924 KB Output is correct
7 Correct 54 ms 32108 KB Output is correct
8 Correct 104 ms 34688 KB Output is correct
9 Correct 352 ms 35716 KB Output is correct
10 Correct 397 ms 35952 KB Output is correct
11 Correct 573 ms 35952 KB Output is correct
12 Correct 1562 ms 35604 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 277 ms 98580 KB Output is correct
3 Correct 295 ms 98584 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 277 ms 98580 KB Output is correct
3 Correct 295 ms 98584 KB Output is correct
4 Correct 51 ms 32040 KB Output is correct
5 Execution timed out 3562 ms 89956 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 31840 KB Output is correct
2 Correct 358 ms 114100 KB Output is correct
3 Correct 340 ms 114240 KB Output is correct
4 Correct 294 ms 114616 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 31840 KB Output is correct
2 Correct 358 ms 114100 KB Output is correct
3 Correct 340 ms 114240 KB Output is correct
4 Correct 294 ms 114616 KB Output is correct
5 Correct 51 ms 32160 KB Output is correct
6 Execution timed out 3564 ms 108372 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 31820 KB Output is correct
2 Correct 266 ms 96612 KB Output is correct
3 Correct 307 ms 96220 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 31820 KB Output is correct
2 Correct 266 ms 96612 KB Output is correct
3 Correct 307 ms 96220 KB Output is correct
4 Correct 55 ms 32032 KB Output is correct
5 Execution timed out 3563 ms 91280 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 31808 KB Output is correct
2 Correct 428 ms 114196 KB Output is correct
3 Correct 336 ms 114168 KB Output is correct
4 Correct 285 ms 114544 KB Output is correct
5 Correct 48 ms 31848 KB Output is correct
6 Correct 259 ms 96624 KB Output is correct
7 Correct 307 ms 96196 KB Output is correct
8 Correct 411 ms 97844 KB Output is correct
9 Correct 390 ms 97792 KB Output is correct
10 Correct 500 ms 103164 KB Output is correct
11 Correct 468 ms 102092 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 31808 KB Output is correct
2 Correct 428 ms 114196 KB Output is correct
3 Correct 336 ms 114168 KB Output is correct
4 Correct 285 ms 114544 KB Output is correct
5 Correct 48 ms 31848 KB Output is correct
6 Correct 259 ms 96624 KB Output is correct
7 Correct 307 ms 96196 KB Output is correct
8 Correct 411 ms 97844 KB Output is correct
9 Correct 390 ms 97792 KB Output is correct
10 Correct 500 ms 103164 KB Output is correct
11 Correct 468 ms 102092 KB Output is correct
12 Correct 48 ms 32076 KB Output is correct
13 Execution timed out 3573 ms 108296 KB Time limit exceeded
14 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 65 ms 34124 KB Output is correct
3 Correct 60 ms 34028 KB Output is correct
4 Correct 70 ms 34184 KB Output is correct
5 Correct 70 ms 34088 KB Output is correct
6 Correct 68 ms 33916 KB Output is correct
7 Correct 48 ms 31820 KB Output is correct
8 Correct 288 ms 98600 KB Output is correct
9 Correct 276 ms 98636 KB Output is correct
10 Correct 45 ms 31820 KB Output is correct
11 Correct 369 ms 114124 KB Output is correct
12 Correct 331 ms 114188 KB Output is correct
13 Correct 305 ms 114676 KB Output is correct
14 Correct 48 ms 31844 KB Output is correct
15 Correct 258 ms 96532 KB Output is correct
16 Correct 299 ms 96204 KB Output is correct
17 Correct 423 ms 97772 KB Output is correct
18 Correct 435 ms 97680 KB Output is correct
19 Correct 499 ms 103336 KB Output is correct
20 Correct 486 ms 102084 KB Output is correct
21 Correct 303 ms 98176 KB Output is correct
22 Correct 285 ms 98104 KB Output is correct
23 Correct 349 ms 98148 KB Output is correct
24 Correct 372 ms 98128 KB Output is correct
25 Correct 527 ms 106252 KB Output is correct
26 Correct 379 ms 95724 KB Output is correct
27 Correct 391 ms 95652 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 65 ms 34124 KB Output is correct
3 Correct 60 ms 34028 KB Output is correct
4 Correct 70 ms 34184 KB Output is correct
5 Correct 70 ms 34088 KB Output is correct
6 Correct 68 ms 33916 KB Output is correct
7 Correct 48 ms 31820 KB Output is correct
8 Correct 288 ms 98600 KB Output is correct
9 Correct 276 ms 98636 KB Output is correct
10 Correct 45 ms 31820 KB Output is correct
11 Correct 369 ms 114124 KB Output is correct
12 Correct 331 ms 114188 KB Output is correct
13 Correct 305 ms 114676 KB Output is correct
14 Correct 48 ms 31844 KB Output is correct
15 Correct 258 ms 96532 KB Output is correct
16 Correct 299 ms 96204 KB Output is correct
17 Correct 423 ms 97772 KB Output is correct
18 Correct 435 ms 97680 KB Output is correct
19 Correct 499 ms 103336 KB Output is correct
20 Correct 486 ms 102084 KB Output is correct
21 Correct 303 ms 98176 KB Output is correct
22 Correct 285 ms 98104 KB Output is correct
23 Correct 349 ms 98148 KB Output is correct
24 Correct 372 ms 98128 KB Output is correct
25 Correct 527 ms 106252 KB Output is correct
26 Correct 379 ms 95724 KB Output is correct
27 Correct 391 ms 95652 KB Output is correct
28 Correct 55 ms 32076 KB Output is correct
29 Correct 102 ms 34636 KB Output is correct
30 Correct 335 ms 35824 KB Output is correct
31 Correct 385 ms 35928 KB Output is correct
32 Correct 594 ms 36068 KB Output is correct
33 Correct 1651 ms 35608 KB Output is correct
34 Correct 56 ms 32980 KB Output is correct
35 Execution timed out 3563 ms 92596 KB Time limit exceeded
36 Halted 0 ms 0 KB -