oj.uz

답안 #734654

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
734654 2023-05-02T18:31:14 Z Sam_a17 Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 83480 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt(x) __builtin_popcount(x)
 
#define pb push_back
#define popf pop_front
#define popb pop_back
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 4e5 + 10, inf = 1e9 + 10, LOG = 21;
vector<pair<int, int>> adj[N];
long long ans[N], sz[N];
vector<int> qq[N], qx[N];
bool pp[N], used[N];
int n, q, compSize;

int up[N][LOG], in[N][LOG], dw[N][LOG];
int par[N], depths[N];

struct query {
  char type;
  int x, y;
};

vector<query> queries;

void dfsik(int node, int parent) {
  for(auto i: adj[node]) {
    if(i.first == parent) continue;

    up[i.first][0] = node;
    for(int j = 1; j < LOG; j++) {
      up[i.first][j] = up[up[i.first][j - 1]][j - 1];
    }


    in[i.first][0] = node;
    if(par[node] > i.second) {
      for(int j = 1; j < LOG; j++) {
        in[i.first][j] = in[in[i.first][j - 1]][j - 1];
      }
    }

    dw[i.first][0] = node;
    if(par[node] < i.second) {
      for(int j = 1; j < LOG; j++) {
        dw[i.first][j] = dw[dw[i.first][j - 1]][j - 1];
      }
    }

    par[i.first] = i.second;
    depths[i.first] = depths[node] + 1;
    dfsik(i.first, node);
  }

}

int lca(int a, int b) {
  if(a == b) {
    return a;
  }

  if(depths[a] > depths[b]) {
    swap(a, b);
  }

  int delta = depths[b] - depths[a];
  for(int i = 0; i < LOG; i++) {
    if(delta & (1 << i)) {
      b = up[b][i];
    }
  }

  if(a == b) {
    return a;
  }

  for(int i = LOG - 1; i >= 0; i--) {
    if(up[a][i] != up[b][i]) {
      a = up[a][i], b = up[b][i];
    }
  }
  return up[a][0];
}

int go_up(int a, int b) {
  for(int i = 0; i < LOG; i++) {
    if(b & (1 << i)) {
      a = up[a][i];
    }
  }
  return a;
}

int chk(int a, int b, int lst, int lim) {
  if(a == b) {
    return 1;
  }

  int ok = 0;
  for(auto i: adj[a]) {
    if(i.second > lim) continue;
    if(i.second > lst) {
      ok |= chk(i.first, b, i.second, lim);
    }
  }
  return ok;
}


bool check(int a, int b, int tt) {
  if(a == b) {
    return true;
  }

  int lc = lca(a, b), ok = 1;
  int first = depths[a] - depths[lc];
  int aa = a;

  for(int i = 0; i < LOG; i++) {
    if(first & (1 << i)) {
      if(!in[aa][i]) {
        ok = 0;
      } else {
        aa = in[aa][i];
      }
    }
  }

  int second = depths[b] - depths[lc];
  int bb = b;
  for(int i = 0; i < LOG; i++) {
    if(second & (1 << i)) {
      if(!dw[bb][i]) {
        ok = 0;
      } else {
        bb = dw[bb][i];
      }
    }
  }

  if(aa != bb) {
    return 0;
  }

  assert(ok == 1);

  if(lc == a || lc == b) {
    // if(lc == a && par[b] > tt) {
      // ok = 0;
    // } else if(lc == b) {

      // int na = go_up(a, first - 1);
      // if(par[na] > tt) {
        // ok = 0;
      // }
    // }
      return chk(a, b, -1, tt);
  } else {

    int na = go_up(a, first - 1);
    int nb = go_up(b, second - 1);

    if(par[na] > par[nb]) {
      ok = 0;
    }

    if(par[b] > tt) {
      ok = 0;
    }

    if(ok) {
      int pr = chk(a, b, -1, tt);
      return pr;
    }
  }

  return ok;
}


void dfs_sz(int node, int parent) {
  sz[node] = 1;
  compSize++;
  for(auto i: adj[node]) {
    if(i.first == parent || used[i.first]) continue;
    dfs_sz(i.first, node);
    sz[node] += sz[i.first];
  }
}

int centroid(int u, int parent) {
  for(auto i: adj[u]) {
    if(i.first == parent || used[i.first]) continue;
    if(sz[i.first] * 2 > compSize) {
      return centroid(i.first, u);
    }
  }
  return u;
}


// bit
struct fenwick {
  int size;
  vector<long long> tree; 

  void init(int size_) {
    tree.assign(size_ + 2, 0);
    size = size_;
  }

  void upd(int u, long long v) {
    while(u <= size) {
      tree[u] += v;
      u += u & (-u);
    }
  }

  long long qry(int u) {
    long long sum = 0;
    while(u > 0) {
      sum += tree[u];
      u -= u & (-u); // lsb
    }
    return sum;
  }

  long long sum(int l, int r) {
    if(l > r) {
      return 0;
    }
    return qry(r) - qry(l - 1);
  }

} ft_inc, ft_dec;

int get_centroid(int u) {
  compSize = 0;
  dfs_sz(u, 0);
  int center = centroid(u, 0);
  return center;
}

vector<int> which_dec;
vector<pair<int, int>> curr_inc, curr_dec;

bool rev = false;

void solve(int node, int parent, int incr, int decr, int lst, int st) {
  if(parent) {
    if(incr != -1) {
      curr_inc.push_back({st, node});
    }

    if(decr != -1) {
      curr_dec.push_back({lst, node});
      which_dec.push_back(lst);
    }
  }

  for(auto i: adj[node]) {
    if(i.first == parent || used[i.first]) continue;

    if(!parent) {
      solve(i.first, node, i.second, i.second, i.second, i.second);
    } else {
      int new_incr = -1, new_decr = -1;
      if(i.second < lst && incr != -1) {
        new_incr = i.second;
      }

      if(i.second > lst && decr != -1) {
        new_decr = i.second;
      }

      solve(i.first, node, new_incr, new_decr, i.second, st);
    }

    if(parent) continue;
    for(auto j: curr_inc) {
      for(auto k: qq[j.second]) {
        if(k < j.first) continue;
        ans[k - 1]++;
        ans[k - 1] += ft_dec.sum(j.first + 1, k);
      }
    }

    for(auto j: curr_dec) {
      ft_dec.upd(j.first, 1);
    }

    //
    curr_inc.clear();
    curr_dec.clear();
  }
}

void centroid_decomposition() {
  queue<int> q;
  q.push(1);

  while(!q.empty()) {
    auto u = q.front();
    q.pop();

    int center = get_centroid(u);
    solve(center, 0, -1, -1, -1, -1);

    for(auto k: qq[center]) {
      ans[k - 1] += ft_dec.sum(1, k - 1);
    }

    for(auto i: which_dec) {
      ft_dec.upd(i, -1);
    }
    which_dec.clear();

    used[center] = true;
    for(auto i: adj[center]) {
      if(used[i.first]) continue;
      q.push(i.first);
    }
  }
}

bool cmp(pair<int, int>& a, pair<int, int>& b) {
  return a.second > b.second;
}

void solve_() {
  cin >> n >> q;
  
  q += n - 1;

  ft_dec.init(N);

  for(int i = 0; i < q; i++) {
    char type; cin >> type;
    int x, y;
    if(type == 'S') {
      cin >> x >> y;
      adj[x].push_back({y, i + 1});
      adj[y].push_back({x, i + 1});
      queries.push_back({type, x, y});
    } else if(type == 'Q') {
      cin >> x >> y, pp[i] = true;
      qx[x].push_back(y);
      queries.push_back({type, x, y});
    } else {
      cin >> x, pp[i] = true;
      qq[x].push_back(i + 1);
      queries.push_back({type, x, -1});
    }
  }

  for(int i = 1; i <= n; i++) {
    sort(all(adj[i]), cmp);
  }

  centroid_decomposition();
  dfsik(1, 0);

  for(int i = 0; i < q; i++) {
    if(!pp[i]) continue;
    if(queries[i].type == 'Q') {
      if(check(queries[i].y, queries[i].x, i + 1)) {
        cout << "yes" << '\n';
      } else {
        cout << "no" << '\n';
      }
    } else {
      cout << ans[i] + 1 << '\n';
    }
  }
}
 
int main() {
  setIO();
 
  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

servers.cpp: In function 'void setIO(std::string)':
servers.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 34408 KB Output is correct
2 Correct 82 ms 35652 KB Output is correct
3 Correct 112 ms 35568 KB Output is correct
4 Correct 86 ms 35776 KB Output is correct
5 Correct 72 ms 35972 KB Output is correct
6 Correct 694 ms 35796 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 34408 KB Output is correct
2 Correct 82 ms 35652 KB Output is correct
3 Correct 112 ms 35568 KB Output is correct
4 Correct 86 ms 35776 KB Output is correct
5 Correct 72 ms 35972 KB Output is correct
6 Correct 694 ms 35796 KB Output is correct
7 Correct 77 ms 34588 KB Output is correct
8 Correct 68 ms 36672 KB Output is correct
9 Correct 87 ms 36604 KB Output is correct
10 Correct 81 ms 36812 KB Output is correct
11 Correct 70 ms 36944 KB Output is correct
12 Correct 384 ms 36832 KB Output is correct

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 34464 KB Output is correct
2 Execution timed out 3576 ms 74164 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 34464 KB Output is correct
2 Execution timed out 3576 ms 74164 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 34468 KB Output is correct
2 Correct 538 ms 82324 KB Output is correct
3 Correct 515 ms 82296 KB Output is correct
4 Execution timed out 3577 ms 83328 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 34468 KB Output is correct
2 Correct 538 ms 82324 KB Output is correct
3 Correct 515 ms 82296 KB Output is correct
4 Execution timed out 3577 ms 83328 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 34468 KB Output is correct
2 Execution timed out 3586 ms 74872 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 34468 KB Output is correct
2 Execution timed out 3586 ms 74872 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 34528 KB Output is correct
2 Correct 487 ms 82264 KB Output is correct
3 Correct 491 ms 82324 KB Output is correct
4 Execution timed out 3563 ms 83480 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 34528 KB Output is correct
2 Correct 487 ms 82264 KB Output is correct
3 Correct 491 ms 82324 KB Output is correct
4 Execution timed out 3563 ms 83480 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 34432 KB Output is correct
2 Correct 73 ms 35616 KB Output is correct
3 Correct 119 ms 35548 KB Output is correct
4 Correct 107 ms 35832 KB Output is correct
5 Correct 72 ms 36044 KB Output is correct
6 Correct 701 ms 35688 KB Output is correct
7 Correct 60 ms 34500 KB Output is correct
8 Execution timed out 3547 ms 74060 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 34432 KB Output is correct
2 Correct 73 ms 35616 KB Output is correct
3 Correct 119 ms 35548 KB Output is correct
4 Correct 107 ms 35832 KB Output is correct
5 Correct 72 ms 36044 KB Output is correct
6 Correct 701 ms 35688 KB Output is correct
7 Correct 60 ms 34500 KB Output is correct
8 Execution timed out 3547 ms 74060 KB Time limit exceeded
9 Halted 0 ms 0 KB -