oj.uz

Submission #656226

# Submission time Handle Problem Language Result Execution time Memory
656226 2022-11-06T15:14:46 Z 600Mihnea Inside information (BOI21_servers) C++17
50 / 100
 3500 ms 117752 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 << sol[i] << "\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 48 ms 31820 KB Output is correct
2 Correct 65 ms 34040 KB Output is correct
3 Correct 57 ms 33996 KB Output is correct
4 Correct 65 ms 34196 KB Output is correct
5 Correct 59 ms 34108 KB Output is correct
6 Correct 60 ms 33900 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31820 KB Output is correct
2 Correct 65 ms 34040 KB Output is correct
3 Correct 57 ms 33996 KB Output is correct
4 Correct 65 ms 34196 KB Output is correct
5 Correct 59 ms 34108 KB Output is correct
6 Correct 60 ms 33900 KB Output is correct
7 Correct 54 ms 32028 KB Output is correct
8 Incorrect 101 ms 35808 KB Extra information in the output file
9 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31892 KB Output is correct
2 Correct 268 ms 98660 KB Output is correct
3 Correct 261 ms 101500 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31892 KB Output is correct
2 Correct 268 ms 98660 KB Output is correct
3 Correct 261 ms 101500 KB Output is correct
4 Correct 52 ms 32972 KB Output is correct
5 Execution timed out 3579 ms 92872 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31800 KB Output is correct
2 Correct 339 ms 114196 KB Output is correct
3 Correct 331 ms 114232 KB Output is correct
4 Correct 276 ms 114524 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31800 KB Output is correct
2 Correct 339 ms 114196 KB Output is correct
3 Correct 331 ms 114232 KB Output is correct
4 Correct 276 ms 114524 KB Output is correct
5 Incorrect 47 ms 32096 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31824 KB Output is correct
2 Correct 264 ms 96584 KB Output is correct
3 Correct 303 ms 96244 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31824 KB Output is correct
2 Correct 264 ms 96584 KB Output is correct
3 Correct 303 ms 96244 KB Output is correct
4 Incorrect 50 ms 32032 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 31820 KB Output is correct
2 Correct 333 ms 114224 KB Output is correct
3 Correct 332 ms 114124 KB Output is correct
4 Correct 283 ms 114572 KB Output is correct
5 Correct 50 ms 31876 KB Output is correct
6 Correct 255 ms 96564 KB Output is correct
7 Correct 301 ms 96304 KB Output is correct
8 Correct 436 ms 97832 KB Output is correct
9 Correct 370 ms 97740 KB Output is correct
10 Correct 450 ms 103148 KB Output is correct
11 Correct 473 ms 102104 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 31820 KB Output is correct
2 Correct 333 ms 114224 KB Output is correct
3 Correct 332 ms 114124 KB Output is correct
4 Correct 283 ms 114572 KB Output is correct
5 Correct 50 ms 31876 KB Output is correct
6 Correct 255 ms 96564 KB Output is correct
7 Correct 301 ms 96304 KB Output is correct
8 Correct 436 ms 97832 KB Output is correct
9 Correct 370 ms 97740 KB Output is correct
10 Correct 450 ms 103148 KB Output is correct
11 Correct 473 ms 102104 KB Output is correct
12 Incorrect 46 ms 32076 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31760 KB Output is correct
2 Correct 63 ms 34036 KB Output is correct
3 Correct 57 ms 33996 KB Output is correct
4 Correct 66 ms 34260 KB Output is correct
5 Correct 60 ms 34088 KB Output is correct
6 Correct 59 ms 33852 KB Output is correct
7 Correct 51 ms 31832 KB Output is correct
8 Correct 261 ms 98852 KB Output is correct
9 Correct 266 ms 101472 KB Output is correct
10 Correct 48 ms 32740 KB Output is correct
11 Correct 353 ms 117652 KB Output is correct
12 Correct 341 ms 117476 KB Output is correct
13 Correct 272 ms 117752 KB Output is correct
14 Correct 48 ms 32736 KB Output is correct
15 Correct 262 ms 99892 KB Output is correct
16 Correct 303 ms 99532 KB Output is correct
17 Correct 392 ms 101232 KB Output is correct
18 Correct 401 ms 101012 KB Output is correct
19 Correct 485 ms 106488 KB Output is correct
20 Correct 486 ms 105408 KB Output is correct
21 Correct 274 ms 101536 KB Output is correct
22 Correct 278 ms 101412 KB Output is correct
23 Correct 352 ms 101404 KB Output is correct
24 Correct 327 ms 101524 KB Output is correct
25 Correct 491 ms 109440 KB Output is correct
26 Correct 371 ms 99152 KB Output is correct
27 Correct 400 ms 98828 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31760 KB Output is correct
2 Correct 63 ms 34036 KB Output is correct
3 Correct 57 ms 33996 KB Output is correct
4 Correct 66 ms 34260 KB Output is correct
5 Correct 60 ms 34088 KB Output is correct
6 Correct 59 ms 33852 KB Output is correct
7 Correct 51 ms 31832 KB Output is correct
8 Correct 261 ms 98852 KB Output is correct
9 Correct 266 ms 101472 KB Output is correct
10 Correct 48 ms 32740 KB Output is correct
11 Correct 353 ms 117652 KB Output is correct
12 Correct 341 ms 117476 KB Output is correct
13 Correct 272 ms 117752 KB Output is correct
14 Correct 48 ms 32736 KB Output is correct
15 Correct 262 ms 99892 KB Output is correct
16 Correct 303 ms 99532 KB Output is correct
17 Correct 392 ms 101232 KB Output is correct
18 Correct 401 ms 101012 KB Output is correct
19 Correct 485 ms 106488 KB Output is correct
20 Correct 486 ms 105408 KB Output is correct
21 Correct 274 ms 101536 KB Output is correct
22 Correct 278 ms 101412 KB Output is correct
23 Correct 352 ms 101404 KB Output is correct
24 Correct 327 ms 101524 KB Output is correct
25 Correct 491 ms 109440 KB Output is correct
26 Correct 371 ms 99152 KB Output is correct
27 Correct 400 ms 98828 KB Output is correct
28 Correct 51 ms 32952 KB Output is correct
29 Incorrect 102 ms 35788 KB Extra information in the output file
30 Halted 0 ms 0 KB -