oj.uz

답안 #1004847

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1004847 2024-06-21T19:05:20 Z aykhn Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 148808 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define inf 0x3F3F3F3F3F3F3F3F
 
const int MXN = 12e4 + 5;
const int mod = 1e9 + 7;
const int LOG = 20;
 
struct BIT
{
  int n;
  vector<int> ft;
  void init(int N)
  {
    n = N + 5;
    ft.assign(n + 5, 0);
  }
  void add(int pos, int val)
  {
    for (pos = pos + 1; pos <= n; pos += pos & -pos) ft[pos] += val;
  }
  int get(int pos, int res = 0)
  {
    for (pos = pos + 1; pos > 0; pos -= pos & -pos) res += ft[pos];
    return res;
  }
};
 
int n, m;
vector<array<int, 2>> adj[MXN];
int used[MXN], sz[MXN];
BIT ft[MXN];
int cent[LOG][MXN], w[LOG][MXN];
int ic[LOG][MXN], dc[LOG][MXN];
vector<array<int, 3>> ed;
array<int, 2> rep[LOG][MXN];
int tim;
 
void getsize(int a, int p)
{
  sz[a] = 1;
  for (array<int, 2> &v : adj[a])
  {
    if (used[v[0]] || v[0] == p) continue;
    getsize(v[0], a);
    sz[a] += sz[v[0]];
  }
}
int findcent(int a, int p, int &curn)
{
  for (array<int, 2> &v : adj[a])
  {
    if (used[v[0]] || v[0] == p) continue;
    if (sz[v[0]] > curn / 2) return findcent(v[0], a, curn); 
  }
  return a;
}
void dfs(int a, int p, int &lvl, int &cc, array<int, 2> &as)
{
  rep[lvl][a] = as;
  cent[lvl][a] = cc;
  for (array<int, 2> &v : adj[a])
  {
    if (used[v[0]] || v[0] == p) continue;
    w[lvl][v[0]] = v[1];
    dfs(v[0], a, lvl, cc, as);
  }
}
void maincent(int a, int lvl)
{
  getsize(a, a);
  int c = findcent(a, a, sz[a]);
  ic[lvl][c] = dc[lvl][c] = 1;
  used[c] = 1;
  cent[lvl][c] = c;
  for (array<int, 2> &v : adj[c])
  {
    if (used[v[0]]) continue;
    w[lvl][v[0]] = v[1];
    dfs(v[0], c, lvl, c, v);
  }
  for (array<int, 2> &v : adj[c])
  {
    if (used[v[0]]) continue;
    maincent(v[0], lvl + 1);
  }
}
 
int nw = 0;
 
void upd(int a, int p, int &lvl)
{
  if (!ic[lvl][a] && !dc[lvl][a]) return;
  nw += ic[lvl][a];
  for (array<int, 2> &v : adj[a])
  {
    if (cent[lvl][v[0]] != cent[lvl][a] || v[0] == p) continue;
    if (v[1] > tim) continue;
    ic[lvl][v[0]] = w[lvl][a] < v[1];
    dc[lvl][v[0]] = w[lvl][a] > v[1];
    upd(v[0], a, lvl);
  }
}
 
int getind(int c, int ind)
{
  int l = 0, r = (int)adj[c].size() - 1;
  while (l < r)
  {
    int mid = (l + r) >> 1;
    if (adj[c][mid][1] >= ind) r = mid;
    else l = mid + 1;
  }
  return l;
}
 
void add(int c, int ind, int val)
{
  ind = getind(c, ind);
  ft[c].add(ind, val);
}

int ans;
void calcans(int a, int p, int w)
{
  ans++;
  for (array<int, 2> &v : adj[a])
  {
    if (v[0] == p || v[1] < w || v[1] > tim) continue;
    calcans(v[0], a, v[1]);
  }
}
int u1[MXN];
void trav(int a, int w)
{
  u1[a] = 1;
  for (array<int, 2> &v : adj[a])
  {
    if (u1[v[0]] || v[1] < w || v[1] > tim) continue;
    trav(v[0], v[1]);
  }
}
signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  ed.resize(n + m - 1);
  for (array<int, 3> &e : ed)
  {
    char ch;
    cin >> ch >> e[1];
    if (ch == 'S')  cin >> e[2], e[0] = 0;
    else if (ch == 'Q') cin >> e[2], e[0] = 1;
    else e[0] = 2;
  }
  for (int i = 0; i < ed.size(); i++)
  {
    array<int, 3> &e = ed[i];
    if (!e[0]) adj[e[1]].push_back({e[2], i}), adj[e[2]].push_back({e[1], i});
  }
  for (int i = 1; i <= n; i++)
  {
    ft[i].init(adj[i].size());
  }
  maincent(1, 0);
  for (tim = 0; tim < ed.size(); tim++)
  {
    array<int, 3> &e = ed[tim];
    int x = e[1], y = e[2];
    if (!e[0])
    {
      for (int i = 0; i < LOG; i++)
      {
        if (!cent[i][x] || !cent[i][y] || cent[i][x] != cent[i][y]) break;
        nw = 0;
        if (cent[i][x] == x) 
        {
          ic[i][y] = 1;
          dc[i][y] = 1;
          upd(y, x, i);
          if (nw) add(cent[i][y], rep[i][y][1], nw);
        }
        else if (cent[i][x] == y) 
        {
          ic[i][x] = 1;
          dc[i][x] = 1;
          upd(x, y, i);
          if (nw) add(cent[i][x], rep[i][x][1], nw);
        }
        else
        {
          int fx = 0, fy = 0;
          if (ic[i][x] && w[i][x] < w[i][y]) ic[i][y] = 1, fy = 1;
          else if (ic[i][y] && w[i][y] < w[i][x]) ic[i][x] = 1, fx = 1;
          if (dc[i][x] && w[i][x] > w[i][y]) dc[i][y] = 1, fy = 1;
          else if (dc[i][y] && w[i][y] > w[i][x]) dc[i][x] = 1, fx = 1;
          if (fx) 
          {
            upd(x, y, i);
            if (nw) add(cent[i][x], rep[i][x][1], nw);
            nw = 0;
          }
          if (fy) 
          {
            upd(y, x, i);
            if (nw) add(cent[i][y], rep[i][y][1], nw);
            nw = 0;
          }
        }
      }
    }
    else if (e[0] == 1)
    {
      fill(u1 + 1, u1 + n + 1, 0);
      trav(e[2], -inf);
      cout << (u1[e[1]] ? "yes\n" : "no\n");
    }
    else
    {
      ans = 0;
      calcans(x, x, -inf);
      cout << ans << '\n';
    }
  }
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:160:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |   for (int i = 0; i < ed.size(); i++)
      |                   ~~^~~~~~~~~~~
servers.cpp:170:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |   for (tim = 0; tim < ed.size(); tim++)
      |                 ~~~~^~~~~~~~~~~

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 43356 KB Output is correct
2 Correct 83 ms 80456 KB Output is correct
3 Correct 130 ms 45648 KB Output is correct
4 Correct 80 ms 84564 KB Output is correct
5 Correct 79 ms 84820 KB Output is correct
6 Correct 814 ms 31056 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 43356 KB Output is correct
2 Correct 83 ms 80456 KB Output is correct
3 Correct 130 ms 45648 KB Output is correct
4 Correct 80 ms 84564 KB Output is correct
5 Correct 79 ms 84820 KB Output is correct
6 Correct 814 ms 31056 KB Output is correct
7 Correct 21 ms 50524 KB Output is correct
8 Correct 60 ms 79952 KB Output is correct
9 Correct 181 ms 45292 KB Output is correct
10 Correct 51 ms 84304 KB Output is correct
11 Correct 55 ms 84516 KB Output is correct
12 Correct 891 ms 31056 KB Output is correct

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 26968 KB Output is correct
2 Execution timed out 3544 ms 53756 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 26968 KB Output is correct
2 Execution timed out 3544 ms 53756 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 49536 KB Output is correct
2 Correct 2283 ms 148692 KB Output is correct
3 Correct 2164 ms 148564 KB Output is correct
4 Execution timed out 3524 ms 147480 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 49536 KB Output is correct
2 Correct 2283 ms 148692 KB Output is correct
3 Correct 2164 ms 148564 KB Output is correct
4 Execution timed out 3524 ms 147480 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 49500 KB Output is correct
2 Execution timed out 3587 ms 138264 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 49500 KB Output is correct
2 Execution timed out 3587 ms 138264 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 49496 KB Output is correct
2 Correct 2133 ms 148488 KB Output is correct
3 Correct 2146 ms 148808 KB Output is correct
4 Execution timed out 3530 ms 147656 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 49496 KB Output is correct
2 Correct 2133 ms 148488 KB Output is correct
3 Correct 2146 ms 148808 KB Output is correct
4 Execution timed out 3530 ms 147656 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 43352 KB Output is correct
2 Correct 76 ms 80468 KB Output is correct
3 Correct 120 ms 45648 KB Output is correct
4 Correct 77 ms 84504 KB Output is correct
5 Correct 70 ms 84644 KB Output is correct
6 Correct 789 ms 31176 KB Output is correct
7 Correct 22 ms 27996 KB Output is correct
8 Execution timed out 3585 ms 56576 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 43352 KB Output is correct
2 Correct 76 ms 80468 KB Output is correct
3 Correct 120 ms 45648 KB Output is correct
4 Correct 77 ms 84504 KB Output is correct
5 Correct 70 ms 84644 KB Output is correct
6 Correct 789 ms 31176 KB Output is correct
7 Correct 22 ms 27996 KB Output is correct
8 Execution timed out 3585 ms 56576 KB Time limit exceeded
9 Halted 0 ms 0 KB -