oj.uz

Submission #1111862

# Submission time Handle Problem Language Result Execution time Memory
1111862 2024-11-13T08:01:47 Z VinhLuu Synchronization (JOI13_synchronization) C++17
100 / 100
 174 ms 46320 KB 
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define fi first
#define se second
using namespace std;

typedef pair<int,int> pii;
const int N = 2e5 + 5;

int n, m, q, in[N], en[N], demin, dp[N], _x[N], _y[N], d[N], edge[N], rev[N], ver[N], be[N], pa[N], head[N], scc = 1, f[22][N], kq[N];
vector<int> p[N];
vector<pair<int,int>> g[N];
bool flag[N];

void pre(int u,int v){
  dp[u] = 1;
  for(auto [j, id] : g[u]) if(j != v){
    ver[j] = id;
    pa[j] = u;
    d[j] = d[u] + 1;
    pre(j, u);
    dp[u] += dp[j];
  }
}

void hld(int u,int v){
  in[u] = ++demin;
  rev[u] = demin;
  be[u] = scc;

  if(!head[scc]) head[scc] = u;

  if(u == 1) for(int i = 0; i <= 18; i ++) f[i][u] = u;
  else{
    f[0][u] = v;
    for(int i = 1; i <= 18; i ++) f[i][u] = f[i - 1][f[i - 1][u]];
  }

  int mx = 0;
  for(auto j : p[u]) if(j != v && dp[j] > dp[mx]) mx = j;

  if(mx) hld(mx, u);

  for(auto j : p[u]) if(j != v && j != mx){
    scc++;
    hld(j, u);
  }

  en[u] = demin;
}
bool kt(int u,int v){
  return in[u] <= in[v] && in[v] <= en[u];
}

int bit[N];
void update(int x,int val){
  for(int i = x; i <= n; i += i & -i) bit[i] += val;
}
int get(int x){
  int ret = 0;
  for(int i = x; i; i -= i & -i) ret += bit[i];
  return ret;
}

int FIND(int u,int x){
  if(u == x) return x;
  if(!flag[ver[x]]) return x;
  int fin = x;
  for(int i = 18; i >= 0; i --) if(kt(u, f[i][x])){
    if(get(in[x]) - get(in[f[i][x]] - 1) != d[x] - d[pa[f[i][x]]]) fin = f[i][x];
    else x = f[i][x];
  }
  return fin;
}

int query(int u){
  while(true){
    if(be[u] == be[1]) return FIND(1, u);
    if(d[u] - d[pa[head[be[u]]]] > get(in[u]) - get(in[head[be[u]]] - 1)){
      return FIND(head[be[u]], u);
    }
    u = pa[head[be[u]]];
  }
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  cin >> n >> m >> q;
  for(int i = 1; i < n; i ++){
    cin >> _x[i] >> _y[i];
    p[_x[i]].push_back(_y[i]);
    p[_y[i]].push_back(_x[i]);
    g[_x[i]].push_back({_y[i], i});
    g[_y[i]].push_back({_x[i], i});
  }
  d[1] = 1;
  pre(1, 0);
  hld(1, 0);

  for(int i = 1; i <= m; i ++) if(in[_x[i]] > in[_y[i]]) swap(_x[i], _y[i]);
  for(int i = 1; i <= n; i ++) kq[i] = 1;

  while(m--){
    int id; cin >> id;
    if(flag[id]){
      int x = _x[id];
      int y = _y[id];
      int rootx = query(x);
//      cerr << id << " " << x << " " << y << " " << rootx << " " << kq[rootx] << " turn off\n";
      kq[y] = kq[rootx];
      edge[id] = kq[y];
//      cerr << " done " << kq[y] << " e\n";
      update(in[y], -1);
      flag[id] = 0;
    }else{
      int x = _x[id];
      int y = _y[id];
      int rootx = query(x);
//      cerr << id << " " << x << " " << y << " " << rootx << " " << kq[rootx] << " turn on\n";
      kq[rootx] = kq[y] + kq[rootx] - edge[id];
//      cerr << " cooked " << kq[rootx] << " e\n";
      update(in[y], 1);
      flag[id] = 1;
    }
  }
  while(q--){
    int x; cin >> x;
//    cerr << x << " " << query(x) << " kt\n";
    cout << kq[query(x)] << "\n";
  }
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:92:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:93:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35152 KB Output is correct
2 Correct 5 ms 31056 KB Output is correct
3 Correct 5 ms 33276 KB Output is correct
4 Correct 4 ms 31056 KB Output is correct
5 Correct 4 ms 27128 KB Output is correct
6 Correct 5 ms 29264 KB Output is correct
7 Correct 12 ms 26576 KB Output is correct
8 Correct 12 ms 26448 KB Output is correct
9 Correct 11 ms 18768 KB Output is correct
10 Correct 105 ms 34540 KB Output is correct
11 Correct 118 ms 36680 KB Output is correct
12 Correct 125 ms 43412 KB Output is correct
13 Correct 59 ms 36980 KB Output is correct
14 Correct 89 ms 39844 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 40008 KB Output is correct
2 Correct 79 ms 42960 KB Output is correct
3 Correct 78 ms 42824 KB Output is correct
4 Correct 86 ms 39244 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16976 KB Output is correct
2 Correct 3 ms 16976 KB Output is correct
3 Correct 4 ms 10832 KB Output is correct
4 Correct 3 ms 14928 KB Output is correct
5 Correct 3 ms 16976 KB Output is correct
6 Correct 4 ms 15184 KB Output is correct
7 Correct 15 ms 21328 KB Output is correct
8 Correct 174 ms 44360 KB Output is correct
9 Correct 171 ms 45128 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 42312 KB Output is correct
2 Correct 132 ms 42484 KB Output is correct
3 Correct 127 ms 44104 KB Output is correct
4 Correct 129 ms 42572 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15100 KB Output is correct
2 Correct 3 ms 16976 KB Output is correct
3 Correct 3 ms 16976 KB Output is correct
4 Correct 3 ms 18876 KB Output is correct
5 Correct 4 ms 16976 KB Output is correct
6 Correct 13 ms 18856 KB Output is correct
7 Correct 123 ms 35400 KB Output is correct
8 Correct 142 ms 46320 KB Output is correct
9 Correct 65 ms 36780 KB Output is correct
10 Correct 120 ms 38216 KB Output is correct
11 Correct 104 ms 36780 KB Output is correct
12 Correct 103 ms 38860 KB Output is correct
13 Correct 138 ms 39752 KB Output is correct