oj.uz

Submission #1005384

# Submission time Handle Problem Language Result Execution time Memory
1005384 2024-06-22T11:44:38 Z aykhn Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 30656 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, {0, 0, 0});
  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++)
  {
    if (!ed[i][0]) adj[ed[i][1]].push_back({ed[i][2], i}), adj[ed[i][2]].push_back({ed[i][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][x], rep[i][x][1], nw);
      //       nw = 0;
      //     }
      //     // assert(fx + fy <= 1);
      //   }
      // }
    }
    else if (e[0] == 1)
    {
      fill(u1 + 1, u1 + n + 1, 0);
      trav(e[2], -inf);
      cout << (u1[e[1]] ? "yes" : "no") << endl;
    }
    else if (e[0] == 2)
    {
      ans = 0;
      // for (int i = 0; i < LOG; i++)
      // {
      //   if (!cent[i][x]) break;
      //   if (cent[i][x] == x) res += ft[x].get(adj[x].size()) + 1;
      //   else
      //   {
      //     if (dc[i][x])
      //     {
      //       int ind = getind(cent[i][x], rep[i][x][1]);
      //       res += ft[cent[i][x]].get(adj[cent[i][x]].size()) - ft[cent[i][x]].get(ind) + 1;
      //     }
      //   }
      // }
      calcans(e[1], e[1], -inf);
      cout << ans << '\n';
    }
  }
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:171: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]
  171 |   for (int i = 0; i < ed.size(); i++)
      |                   ~~^~~~~~~~~~~
servers.cpp:180: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]
  180 |   for (tim = 0; tim < ed.size(); tim++)
      |                 ~~~~^~~~~~~~~~~
servers.cpp:183:9: warning: unused variable 'x' [-Wunused-variable]
  183 |     int x = e[1], y = e[2];
      |         ^
servers.cpp:183:19: warning: unused variable 'y' [-Wunused-variable]
  183 |     int x = e[1], y = e[2];
      |                   ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 135 ms 17488 KB Output is correct
2 Correct 185 ms 18512 KB Output is correct
3 Correct 255 ms 18504 KB Output is correct
4 Correct 197 ms 18512 KB Output is correct
5 Correct 194 ms 18552 KB Output is correct
6 Correct 999 ms 18512 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 135 ms 17488 KB Output is correct
2 Correct 185 ms 18512 KB Output is correct
3 Correct 255 ms 18504 KB Output is correct
4 Correct 197 ms 18512 KB Output is correct
5 Correct 194 ms 18552 KB Output is correct
6 Correct 999 ms 18512 KB Output is correct
7 Correct 126 ms 17492 KB Output is correct
8 Correct 112 ms 18012 KB Output is correct
9 Correct 240 ms 18232 KB Output is correct
10 Correct 109 ms 18168 KB Output is correct
11 Correct 109 ms 18220 KB Output is correct
12 Correct 902 ms 18200 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 137 ms 17488 KB Output is correct
2 Execution timed out 3568 ms 27988 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 137 ms 17488 KB Output is correct
2 Execution timed out 3568 ms 27988 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 17488 KB Output is correct
2 Correct 2562 ms 29500 KB Output is correct
3 Correct 2281 ms 29392 KB Output is correct
4 Execution timed out 3563 ms 30656 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 17488 KB Output is correct
2 Correct 2562 ms 29500 KB Output is correct
3 Correct 2281 ms 29392 KB Output is correct
4 Execution timed out 3563 ms 30656 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 17488 KB Output is correct
2 Execution timed out 3561 ms 29780 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 17488 KB Output is correct
2 Execution timed out 3561 ms 29780 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 132 ms 17492 KB Output is correct
2 Correct 2413 ms 29524 KB Output is correct
3 Correct 2395 ms 29336 KB Output is correct
4 Execution timed out 3524 ms 30340 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 132 ms 17492 KB Output is correct
2 Correct 2413 ms 29524 KB Output is correct
3 Correct 2395 ms 29336 KB Output is correct
4 Execution timed out 3524 ms 30340 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 130 ms 17492 KB Output is correct
2 Correct 196 ms 18480 KB Output is correct
3 Correct 260 ms 18500 KB Output is correct
4 Correct 199 ms 18512 KB Output is correct
5 Correct 193 ms 18568 KB Output is correct
6 Correct 1026 ms 18516 KB Output is correct
7 Correct 131 ms 17488 KB Output is correct
8 Execution timed out 3593 ms 28096 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 130 ms 17492 KB Output is correct
2 Correct 196 ms 18480 KB Output is correct
3 Correct 260 ms 18500 KB Output is correct
4 Correct 199 ms 18512 KB Output is correct
5 Correct 193 ms 18568 KB Output is correct
6 Correct 1026 ms 18516 KB Output is correct
7 Correct 131 ms 17488 KB Output is correct
8 Execution timed out 3593 ms 28096 KB Time limit exceeded
9 Halted 0 ms 0 KB -