oj.uz

Submission #656225

# Submission time Handle Problem Language Result Execution time Memory
656225 2022-11-06T15:09:00 Z 600Mihnea Inside information (BOI21_servers) C++17
30 / 100
 3500 ms 117884 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(a, b, 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 50 ms 31800 KB Output is correct
2 Correct 85 ms 35412 KB Output is correct
3 Correct 78 ms 35404 KB Output is correct
4 Correct 68 ms 35596 KB Output is correct
5 Correct 60 ms 35576 KB Output is correct
6 Correct 261 ms 35248 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31800 KB Output is correct
2 Correct 85 ms 35412 KB Output is correct
3 Correct 78 ms 35404 KB Output is correct
4 Correct 68 ms 35596 KB Output is correct
5 Correct 60 ms 35576 KB Output is correct
6 Correct 261 ms 35248 KB Output is correct
7 Runtime error 71 ms 64844 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31904 KB Output is correct
2 Execution timed out 3547 ms 90624 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31904 KB Output is correct
2 Execution timed out 3547 ms 90624 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 31760 KB Output is correct
2 Correct 335 ms 117528 KB Output is correct
3 Correct 336 ms 117560 KB Output is correct
4 Correct 285 ms 117884 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 31760 KB Output is correct
2 Correct 335 ms 117528 KB Output is correct
3 Correct 336 ms 117560 KB Output is correct
4 Correct 285 ms 117884 KB Output is correct
5 Runtime error 70 ms 64844 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31852 KB Output is correct
2 Correct 262 ms 99872 KB Output is correct
3 Correct 367 ms 99572 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 31852 KB Output is correct
2 Correct 262 ms 99872 KB Output is correct
3 Correct 367 ms 99572 KB Output is correct
4 Runtime error 70 ms 64900 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31776 KB Output is correct
2 Correct 349 ms 117456 KB Output is correct
3 Correct 352 ms 117452 KB Output is correct
4 Correct 302 ms 117876 KB Output is correct
5 Correct 61 ms 32644 KB Output is correct
6 Correct 272 ms 99812 KB Output is correct
7 Correct 314 ms 99440 KB Output is correct
8 Correct 490 ms 101128 KB Output is correct
9 Correct 516 ms 101080 KB Output is correct
10 Correct 580 ms 106540 KB Output is correct
11 Correct 624 ms 105412 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 31776 KB Output is correct
2 Correct 349 ms 117456 KB Output is correct
3 Correct 352 ms 117452 KB Output is correct
4 Correct 302 ms 117876 KB Output is correct
5 Correct 61 ms 32644 KB Output is correct
6 Correct 272 ms 99812 KB Output is correct
7 Correct 314 ms 99440 KB Output is correct
8 Correct 490 ms 101128 KB Output is correct
9 Correct 516 ms 101080 KB Output is correct
10 Correct 580 ms 106540 KB Output is correct
11 Correct 624 ms 105412 KB Output is correct
12 Runtime error 68 ms 64844 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31796 KB Output is correct
2 Correct 79 ms 35432 KB Output is correct
3 Correct 80 ms 35468 KB Output is correct
4 Correct 69 ms 35628 KB Output is correct
5 Correct 60 ms 35532 KB Output is correct
6 Correct 168 ms 35248 KB Output is correct
7 Correct 55 ms 32672 KB Output is correct
8 Execution timed out 3582 ms 90744 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31796 KB Output is correct
2 Correct 79 ms 35432 KB Output is correct
3 Correct 80 ms 35468 KB Output is correct
4 Correct 69 ms 35628 KB Output is correct
5 Correct 60 ms 35532 KB Output is correct
6 Correct 168 ms 35248 KB Output is correct
7 Correct 55 ms 32672 KB Output is correct
8 Execution timed out 3582 ms 90744 KB Time limit exceeded
9 Halted 0 ms 0 KB -