Submission #1111862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111862		VinhLuu	Synchronization (JOI13_synchronization)	C++17	100 / 100	174 ms	46320 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40