oj.uz

답안 #734665

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
734665 2023-05-02T18:53:41 Z Sam_a17 Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 64812 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], dw[N];
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];
    }

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

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

    if(parent) {
      if(i.second < par[node]) {
        in[i.first] = in[node] + 1;
      } else {
        in[i.first] = 1;
      }

      if(i.second > par[node]) {
        dw[i.first] = dw[node] + 1;
      } else {
        dw[i.first] = 1;
      }
    }

    dfs1(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];
  if(in[a] < first) {
    ok = 0;
  }

  int second = depths[b] - depths[lc];
  if(dw[b] < second) {
    ok = 0;
  }

  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) {
      return chk(a, b, -1, tt);
    // }
  }

  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);
  }

  dfsik(1, 0);
  dfs1(1, 0);
  centroid_decomposition();

  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 49 ms 34400 KB Output is correct
2 Correct 71 ms 35112 KB Output is correct
3 Correct 131 ms 34912 KB Output is correct
4 Correct 73 ms 35132 KB Output is correct
5 Correct 69 ms 35332 KB Output is correct
6 Correct 1047 ms 35140 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 34400 KB Output is correct
2 Correct 71 ms 35112 KB Output is correct
3 Correct 131 ms 34912 KB Output is correct
4 Correct 73 ms 35132 KB Output is correct
5 Correct 69 ms 35332 KB Output is correct
6 Correct 1047 ms 35140 KB Output is correct
7 Correct 52 ms 34648 KB Output is correct
8 Correct 66 ms 36068 KB Output is correct
9 Correct 86 ms 35972 KB Output is correct
10 Correct 70 ms 36156 KB Output is correct
11 Correct 62 ms 36384 KB Output is correct
12 Correct 560 ms 36020 KB Output is correct

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 34428 KB Output is correct
2 Execution timed out 3566 ms 54484 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 34428 KB Output is correct
2 Execution timed out 3566 ms 54484 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 34436 KB Output is correct
2 Correct 429 ms 63496 KB Output is correct
3 Correct 407 ms 63480 KB Output is correct
4 Execution timed out 3562 ms 64652 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 34436 KB Output is correct
2 Correct 429 ms 63496 KB Output is correct
3 Correct 407 ms 63480 KB Output is correct
4 Execution timed out 3562 ms 64652 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 34432 KB Output is correct
2 Correct 419 ms 63400 KB Output is correct
3 Correct 403 ms 63480 KB Output is correct
4 Execution timed out 3554 ms 64812 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 34432 KB Output is correct
2 Correct 419 ms 63400 KB Output is correct
3 Correct 403 ms 63480 KB Output is correct
4 Execution timed out 3554 ms 64812 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 34436 KB Output is correct
2 Correct 74 ms 35092 KB Output is correct
3 Correct 143 ms 34956 KB Output is correct
4 Correct 71 ms 35116 KB Output is correct
5 Correct 67 ms 35348 KB Output is correct
6 Correct 1034 ms 35116 KB Output is correct
7 Correct 51 ms 34420 KB Output is correct
8 Execution timed out 3557 ms 54356 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 34436 KB Output is correct
2 Correct 74 ms 35092 KB Output is correct
3 Correct 143 ms 34956 KB Output is correct
4 Correct 71 ms 35116 KB Output is correct
5 Correct 67 ms 35348 KB Output is correct
6 Correct 1034 ms 35116 KB Output is correct
7 Correct 51 ms 34420 KB Output is correct
8 Execution timed out 3557 ms 54356 KB Time limit exceeded
9 Halted 0 ms 0 KB -