oj.uz

Submission #1004857

# Submission time Handle Problem Language Result Execution time Memory
1004857 2024-06-21T19:44:59 Z aykhn Inside information (BOI21_servers) C++17
2.5 / 100
 3500 ms 145320 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++)
  {
    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][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)
    {
      int res = 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;
      //     }
      //   }
      // }
      cout << res << endl;
    }
  }
}

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++)
      |                 ~~~~^~~~~~~~~~~
servers.cpp:173:9: warning: unused variable 'x' [-Wunused-variable]
  173 |     int x = e[1], y = e[2];
      |         ^
servers.cpp:173:19: warning: unused variable 'y' [-Wunused-variable]
  173 |     int x = e[1], y = e[2];
      |                   ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 143 ms 43348 KB Output is correct
2 Correct 201 ms 78928 KB Output is correct
3 Correct 260 ms 44112 KB Output is correct
4 Correct 208 ms 83268 KB Output is correct
5 Correct 197 ms 83280 KB Output is correct
6 Correct 954 ms 29780 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 143 ms 43348 KB Output is correct
2 Correct 201 ms 78928 KB Output is correct
3 Correct 260 ms 44112 KB Output is correct
4 Correct 208 ms 83268 KB Output is correct
5 Correct 197 ms 83280 KB Output is correct
6 Correct 954 ms 29780 KB Output is correct
7 Incorrect 141 ms 49488 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 133 ms 26892 KB Output is correct
2 Execution timed out 3602 ms 53764 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 133 ms 26892 KB Output is correct
2 Execution timed out 3602 ms 53764 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 49652 KB Output is correct
2 Correct 2297 ms 145232 KB Output is correct
3 Correct 2266 ms 145196 KB Output is correct
4 Execution timed out 3537 ms 144324 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 49652 KB Output is correct
2 Correct 2297 ms 145232 KB Output is correct
3 Correct 2266 ms 145196 KB Output is correct
4 Execution timed out 3537 ms 144324 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 49640 KB Output is correct
2 Execution timed out 3567 ms 134996 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 49640 KB Output is correct
2 Execution timed out 3567 ms 134996 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 112 ms 49488 KB Output is correct
2 Correct 2244 ms 145320 KB Output is correct
3 Correct 2283 ms 145280 KB Output is correct
4 Execution timed out 3571 ms 144224 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 112 ms 49488 KB Output is correct
2 Correct 2244 ms 145320 KB Output is correct
3 Correct 2283 ms 145280 KB Output is correct
4 Execution timed out 3571 ms 144224 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 132 ms 43348 KB Output is correct
2 Correct 200 ms 78932 KB Output is correct
3 Correct 240 ms 44116 KB Output is correct
4 Correct 187 ms 83284 KB Output is correct
5 Correct 197 ms 83432 KB Output is correct
6 Correct 906 ms 29776 KB Output is correct
7 Correct 125 ms 26960 KB Output is correct
8 Execution timed out 3545 ms 53748 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 132 ms 43348 KB Output is correct
2 Correct 200 ms 78932 KB Output is correct
3 Correct 240 ms 44116 KB Output is correct
4 Correct 187 ms 83284 KB Output is correct
5 Correct 197 ms 83432 KB Output is correct
6 Correct 906 ms 29776 KB Output is correct
7 Correct 125 ms 26960 KB Output is correct
8 Execution timed out 3545 ms 53748 KB Time limit exceeded
9 Halted 0 ms 0 KB -