oj.uz

답안 #734667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
734667 2023-05-02T18:55:33 Z Sam_a17 Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 68736 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(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(!ok) {
    return ok;
  }

  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 = 1; i <= n; i++) {
    dbg(make_pair(in[i], dw[i]))
  }
  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 48 ms 34432 KB Output is correct
2 Correct 111 ms 35216 KB Output is correct
3 Correct 148 ms 35132 KB Output is correct
4 Correct 105 ms 35464 KB Output is correct
5 Correct 102 ms 35456 KB Output is correct
6 Correct 1268 ms 35444 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 34432 KB Output is correct
2 Correct 111 ms 35216 KB Output is correct
3 Correct 148 ms 35132 KB Output is correct
4 Correct 105 ms 35464 KB Output is correct
5 Correct 102 ms 35456 KB Output is correct
6 Correct 1268 ms 35444 KB Output is correct
7 Correct 48 ms 34660 KB Output is correct
8 Correct 94 ms 36208 KB Output is correct
9 Correct 119 ms 36028 KB Output is correct
10 Correct 132 ms 36344 KB Output is correct
11 Correct 93 ms 36468 KB Output is correct
12 Correct 717 ms 36372 KB Output is correct

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 34432 KB Output is correct
2 Execution timed out 3550 ms 58932 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 34432 KB Output is correct
2 Execution timed out 3550 ms 58932 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 34464 KB Output is correct
2 Correct 1534 ms 67084 KB Output is correct
3 Correct 1625 ms 67112 KB Output is correct
4 Execution timed out 3560 ms 68732 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 34464 KB Output is correct
2 Correct 1534 ms 67084 KB Output is correct
3 Correct 1625 ms 67112 KB Output is correct
4 Execution timed out 3560 ms 68732 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 34432 KB Output is correct
2 Correct 1607 ms 67036 KB Output is correct
3 Correct 1654 ms 67076 KB Output is correct
4 Execution timed out 3548 ms 68736 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 34432 KB Output is correct
2 Correct 1607 ms 67036 KB Output is correct
3 Correct 1654 ms 67076 KB Output is correct
4 Execution timed out 3548 ms 68736 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 34460 KB Output is correct
2 Correct 106 ms 35196 KB Output is correct
3 Correct 153 ms 35108 KB Output is correct
4 Correct 115 ms 35328 KB Output is correct
5 Correct 113 ms 35488 KB Output is correct
6 Correct 1276 ms 35296 KB Output is correct
7 Correct 59 ms 34516 KB Output is correct
8 Execution timed out 3543 ms 58800 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 34460 KB Output is correct
2 Correct 106 ms 35196 KB Output is correct
3 Correct 153 ms 35108 KB Output is correct
4 Correct 115 ms 35328 KB Output is correct
5 Correct 113 ms 35488 KB Output is correct
6 Correct 1276 ms 35296 KB Output is correct
7 Correct 59 ms 34516 KB Output is correct
8 Execution timed out 3543 ms 58800 KB Time limit exceeded
9 Halted 0 ms 0 KB -