Submission #1185601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185601		epicci23	Grapevine (NOI22_grapevine)	C++20	100 / 100	514 ms	52416 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int INF = 1e18;
const int INF2 = 5e15;
const int N = 1e5 + 5;

vector<array<int,2>> Edges; // first element is Xor of edge points, second element is weight
vector<int> v[N],eski;
map<array<int,2>,int> mp;
int n, q, depth[N], sub[N], vis[N], mark[N], ans[N], tin[N], tout[N], ti, comp;
vector<int> Ac[N], Sor[N];
vector<array<int,2>> Degis[N];

vector<int> add, seg, lazy, base;

void init(int _n){
  seg.assign(4 * _n + 5, INF);
  add.assign(_n + 5, 0);
  lazy.assign(4 * _n + 5, 0);
  base.assign(_n + 5, 0);
}

inline void push(int rt,int l,int r){
  if(lazy[rt] == 0) return;
  int u = lazy[rt];
  lazy[rt] = 0;
  seg[rt] += u;
  if(l == r){
   add[l] += u;
   return;
  }
  lazy[rt * 2] += u;
  lazy[rt * 2 + 1] += u;
}

void upd(int rt,int l,int r,int gl,int gr,int u){
  if(l > r || gl > gr) return;
  push(rt, l, r);
  if(r < gl || l > gr) return;
  if(l >= gl && r <= gr){
    lazy[rt] += u;
    push(rt, l, r);
    return;
  }
  int mid = (l + r) / 2;
  upd(rt * 2, l, mid, gl, gr, u); upd(rt * 2 + 1, mid + 1, r, gl, gr, u);
  seg[rt] = min(seg[rt * 2], seg[rt * 2 + 1]);
}

int Find(int rt,int l,int r,int ind){
  push(rt, l, r);
  if(l == r) return base[l] + add[l];
  int mid = (l + r) / 2;
  if(ind <= mid) return Find(rt * 2, l, mid, ind);
  return Find(rt * 2 + 1, mid + 1, r, ind);
}

void Open(int rt,int l,int r,int ind){
  push(rt, l, r);
  if(r < ind || l > ind) return;
  if(l == r){
    seg[rt] = add[l] + base[l];
    return;
  }
  int mid = (l + r) / 2;
  Open(rt * 2, l, mid, ind), Open(rt * 2 + 1, mid + 1, r, ind);
  seg[rt] = min(seg[rt * 2], seg[rt * 2 + 1]);
}

void Close(int rt,int l,int r,int ind){
  push(rt, l, r);
  if(r < ind || l > ind) return;
  if(l == r){
    seg[rt] = INF;
    return;
  }
  int mid = (l + r) / 2;
  Close(rt * 2, l, mid, ind), Close(rt * 2 + 1, mid + 1, r, ind);
  seg[rt] = min(seg[rt * 2], seg[rt * 2 + 1]);
}

void hehe(int c,int p){
 sub[c] = 1;
 comp++;
 for(int ind : v[c]){
   int u = Edges[ind][0] ^ c;
   if(u == p || vis[u]) continue;
   hehe(u, c);
   sub[c] += sub[u];
 }
}

int Find_Centroid(int c,int p){
 for(int ind : v[c]){
   int u = Edges[ind][0] ^ c;
   if(u == p || vis[u] || comp / 2 > sub[u]) continue;
   return Find_Centroid(u, c);
 }
 return c;
}

vector<array<int,3>> Events;

void dep(int c,int p,int d){
  tin[c] = ++ti;
  depth[c] = base[ti] = d;
  //cout << "suann : " << c << ' ' << d << '\n';
  mark[c] = 0;
  for(int u : Sor[c]) Events.push_back({u, c, -1});
  for(int u : Ac[c]) Events.push_back({u, c, -2});
  for(int ind : v[c]){
    int u = Edges[ind][0] ^ c;
    if(u == p || vis[u]) continue;
    for(auto X : Degis[ind]) Events.push_back({X[0], X[1], u});
    dep(u, c, d + eski[ind]);
  }
  tout[c] = ti;
}

void calc(int c,int p){
  ti = comp = 0;
  hehe(c, p);
  c = Find_Centroid(c, p);
  init(comp + 5);
  
  //cout << "root : " << c << '\n';

  Events.clear();
  dep(c, p, 0);
  sort(all(Events));

  for(auto X : Events){
  	if(X[2] == -1){
      ans[X[0]] = min(ans[X[0]], Find(1,1,comp,tin[X[1]]) + seg[1]);
  	}
  	else if(X[2] == -2){
      if(mark[X[1]]) Close(1,1,comp,tin[X[1]]);
      else Open(1,1,comp,tin[X[1]]);
      mark[X[1]] ^= 1;
  	}
  	else{
  	  //cout << 1 << ' ' << comp << ' ' << tin[X[2]] << ' ' << tout[X[2]] << ' ' << X[1] << '\n';
      upd(1,1,comp,tin[X[2]],tout[X[2]],X[1]);
  	}
  }

  vis[c] = 1;
  for(int ind : v[c]){
  	int u = Edges[ind][0] ^ c;
  	if(vis[u] || u == p) continue;
  	calc(u, c);
  }
}

void _(){
  cin >> n >> q;
  for(int i=0;i+1<n;i++){
  	int a,b,c;
  	cin >> a >> b >> c;
  	v[a].push_back(sz(Edges));
  	v[b].push_back(sz(Edges));
  	eski.push_back(c);
  	Edges.push_back({a ^ b, c});
    mp[{a, b}] = mp[{b, a}] = i;
  }

  vector<int> Haha;

  for(int i=1;i<=q;i++){
    int op;
    cin >> op;
    if(op == 1){
      int node; cin >> node;
      Haha.push_back(i);
      ans[i] = INF;
      Sor[node].push_back(i);
    }
    else if(op == 2){
      int node; cin >> node;
      Ac[node].push_back(i);
    }
    else{
      int a, b, c;
      cin >> a >> b >> c;
      int ind = mp[{a, b}];
      //cout << "noldu : " << c - Edges[ind][1] << '\n';
      Degis[ind].push_back({i, c - Edges[ind][1]});
      Edges[ind][1] = c;
    }
  }

  calc(1, -1);
  for(int hmhm : Haha){
  	if(ans[hmhm] >= INF2) cout << -1 << '\n';
  	else cout << ans[hmhm] << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 18 / 18
• Subtask 6: 32 / 32