oj.uz

답안 #656238

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656238 2022-11-06T15:39:39 Z 600Mihnea Inside information (BOI21_servers) C++17
50 / 100
 519 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];
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>> ts;

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);
      ts.push_back({T, send});
    }
  }
}

void cdecomp(int a) {
  ts.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;
  for (auto &jj : ts) {
    int T = jj.first, send = jj.second;

    for (auto &some : all) {
      if (send < some.start && some.finish < T) {
        sol[T]++;
      }
    }
  }
  {
    /// 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);
    }
  }

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

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 31820 KB Output is correct
2 Correct 66 ms 34068 KB Output is correct
3 Correct 59 ms 34056 KB Output is correct
4 Correct 69 ms 34272 KB Output is correct
5 Correct 62 ms 34080 KB Output is correct
6 Correct 62 ms 33952 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 31820 KB Output is correct
2 Correct 66 ms 34068 KB Output is correct
3 Correct 59 ms 34056 KB Output is correct
4 Correct 69 ms 34272 KB Output is correct
5 Correct 62 ms 34080 KB Output is correct
6 Correct 62 ms 33952 KB Output is correct
7 Incorrect 53 ms 31820 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 31872 KB Output is correct
2 Correct 291 ms 99992 KB Output is correct
3 Correct 283 ms 100004 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 31872 KB Output is correct
2 Correct 291 ms 99992 KB Output is correct
3 Correct 283 ms 100004 KB Output is correct
4 Incorrect 51 ms 31836 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 31744 KB Output is correct
2 Correct 357 ms 114184 KB Output is correct
3 Correct 363 ms 114132 KB Output is correct
4 Correct 283 ms 114468 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 31744 KB Output is correct
2 Correct 357 ms 114184 KB Output is correct
3 Correct 363 ms 114132 KB Output is correct
4 Correct 283 ms 114468 KB Output is correct
5 Incorrect 49 ms 31760 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 31756 KB Output is correct
2 Correct 270 ms 97120 KB Output is correct
3 Correct 311 ms 96216 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 31756 KB Output is correct
2 Correct 270 ms 97120 KB Output is correct
3 Correct 311 ms 96216 KB Output is correct
4 Incorrect 67 ms 31836 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 31772 KB Output is correct
2 Correct 401 ms 114276 KB Output is correct
3 Correct 409 ms 114212 KB Output is correct
4 Correct 359 ms 114676 KB Output is correct
5 Correct 56 ms 31744 KB Output is correct
6 Correct 322 ms 97076 KB Output is correct
7 Correct 308 ms 96248 KB Output is correct
8 Correct 421 ms 97768 KB Output is correct
9 Correct 376 ms 97728 KB Output is correct
10 Correct 504 ms 103164 KB Output is correct
11 Correct 519 ms 102080 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 31772 KB Output is correct
2 Correct 401 ms 114276 KB Output is correct
3 Correct 409 ms 114212 KB Output is correct
4 Correct 359 ms 114676 KB Output is correct
5 Correct 56 ms 31744 KB Output is correct
6 Correct 322 ms 97076 KB Output is correct
7 Correct 308 ms 96248 KB Output is correct
8 Correct 421 ms 97768 KB Output is correct
9 Correct 376 ms 97728 KB Output is correct
10 Correct 504 ms 103164 KB Output is correct
11 Correct 519 ms 102080 KB Output is correct
12 Incorrect 48 ms 31820 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 31848 KB Output is correct
2 Correct 71 ms 34088 KB Output is correct
3 Correct 70 ms 33996 KB Output is correct
4 Correct 72 ms 34288 KB Output is correct
5 Correct 61 ms 34108 KB Output is correct
6 Correct 61 ms 33880 KB Output is correct
7 Correct 52 ms 31820 KB Output is correct
8 Correct 271 ms 99960 KB Output is correct
9 Correct 272 ms 99928 KB Output is correct
10 Correct 46 ms 31820 KB Output is correct
11 Correct 343 ms 114140 KB Output is correct
12 Correct 340 ms 114220 KB Output is correct
13 Correct 308 ms 114572 KB Output is correct
14 Correct 50 ms 31740 KB Output is correct
15 Correct 314 ms 97112 KB Output is correct
16 Correct 302 ms 96168 KB Output is correct
17 Correct 471 ms 97692 KB Output is correct
18 Correct 385 ms 97796 KB Output is correct
19 Correct 511 ms 103156 KB Output is correct
20 Correct 513 ms 102204 KB Output is correct
21 Correct 315 ms 98780 KB Output is correct
22 Correct 310 ms 98712 KB Output is correct
23 Correct 402 ms 98184 KB Output is correct
24 Correct 335 ms 98252 KB Output is correct
25 Correct 495 ms 104616 KB Output is correct
26 Correct 414 ms 95776 KB Output is correct
27 Correct 389 ms 95400 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 31848 KB Output is correct
2 Correct 71 ms 34088 KB Output is correct
3 Correct 70 ms 33996 KB Output is correct
4 Correct 72 ms 34288 KB Output is correct
5 Correct 61 ms 34108 KB Output is correct
6 Correct 61 ms 33880 KB Output is correct
7 Correct 52 ms 31820 KB Output is correct
8 Correct 271 ms 99960 KB Output is correct
9 Correct 272 ms 99928 KB Output is correct
10 Correct 46 ms 31820 KB Output is correct
11 Correct 343 ms 114140 KB Output is correct
12 Correct 340 ms 114220 KB Output is correct
13 Correct 308 ms 114572 KB Output is correct
14 Correct 50 ms 31740 KB Output is correct
15 Correct 314 ms 97112 KB Output is correct
16 Correct 302 ms 96168 KB Output is correct
17 Correct 471 ms 97692 KB Output is correct
18 Correct 385 ms 97796 KB Output is correct
19 Correct 511 ms 103156 KB Output is correct
20 Correct 513 ms 102204 KB Output is correct
21 Correct 315 ms 98780 KB Output is correct
22 Correct 310 ms 98712 KB Output is correct
23 Correct 402 ms 98184 KB Output is correct
24 Correct 335 ms 98252 KB Output is correct
25 Correct 495 ms 104616 KB Output is correct
26 Correct 414 ms 95776 KB Output is correct
27 Correct 389 ms 95400 KB Output is correct
28 Incorrect 53 ms 31816 KB Extra information in the output file
29 Halted 0 ms 0 KB -