oj.uz

Submission #1004859

# Submission time Handle Problem Language Result Execution time Memory
1004859 2024-06-21T19:48:20 Z aykhn Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 27468 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 119 ms 16724 KB Output is correct
2 Correct 164 ms 17144 KB Output is correct
3 Correct 231 ms 17236 KB Output is correct
4 Correct 170 ms 16976 KB Output is correct
5 Correct 182 ms 16976 KB Output is correct
6 Correct 870 ms 16980 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 119 ms 16724 KB Output is correct
2 Correct 164 ms 17144 KB Output is correct
3 Correct 231 ms 17236 KB Output is correct
4 Correct 170 ms 16976 KB Output is correct
5 Correct 182 ms 16976 KB Output is correct
6 Correct 870 ms 16980 KB Output is correct
7 Correct 107 ms 16720 KB Output is correct
8 Correct 95 ms 16976 KB Output is correct
9 Correct 217 ms 17244 KB Output is correct
10 Correct 93 ms 16980 KB Output is correct
11 Correct 101 ms 16976 KB Output is correct
12 Correct 810 ms 17056 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 114 ms 16724 KB Output is correct
2 Execution timed out 3553 ms 25096 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 114 ms 16724 KB Output is correct
2 Execution timed out 3553 ms 25096 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 16724 KB Output is correct
2 Correct 2071 ms 26052 KB Output is correct
3 Correct 1976 ms 26188 KB Output is correct
4 Execution timed out 3521 ms 27468 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 16724 KB Output is correct
2 Correct 2071 ms 26052 KB Output is correct
3 Correct 1976 ms 26188 KB Output is correct
4 Execution timed out 3521 ms 27468 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 116 ms 16768 KB Output is correct
2 Correct 1996 ms 25980 KB Output is correct
3 Correct 2122 ms 26020 KB Output is correct
4 Execution timed out 3539 ms 27280 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 116 ms 16768 KB Output is correct
2 Correct 1996 ms 25980 KB Output is correct
3 Correct 2122 ms 26020 KB Output is correct
4 Execution timed out 3539 ms 27280 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 115 ms 16820 KB Output is correct
2 Correct 174 ms 16980 KB Output is correct
3 Correct 228 ms 17232 KB Output is correct
4 Correct 170 ms 16976 KB Output is correct
5 Correct 170 ms 16980 KB Output is correct
6 Correct 844 ms 17044 KB Output is correct
7 Correct 119 ms 16724 KB Output is correct
8 Execution timed out 3584 ms 25024 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 115 ms 16820 KB Output is correct
2 Correct 174 ms 16980 KB Output is correct
3 Correct 228 ms 17232 KB Output is correct
4 Correct 170 ms 16976 KB Output is correct
5 Correct 170 ms 16980 KB Output is correct
6 Correct 844 ms 17044 KB Output is correct
7 Correct 119 ms 16724 KB Output is correct
8 Execution timed out 3584 ms 25024 KB Time limit exceeded
9 Halted 0 ms 0 KB -