Submission #1264556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264556		_rain_	Grapevine (NOI22_grapevine)	C++20	18 / 100	1370 ms	182288 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define sz(s) (int)(s).size()
#define MASK(x) ((LL)(1)<<(x))
#define BIT(mask,x) (((mask)>>(x))&(1))

template<class X,class Y>
	bool maximize(X &x ,Y y){
		if (x < y) return x = y , true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x ,Y y){
		if (x > y) return x = y , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
		return;
	}
template<class X,class Y>
	Y Find(vector<X>&data,Y y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}	
	
const int N = (int) 1e5;
const int MAXLOG = (int) 18;	
const LL inf  = (LL)1e18;
	int x[N + 2] , y[N + 2] , w[N + 2];
	int sta[MAXLOG + 2][N + 2] = {} , fin[MAXLOG + 2][N + 2] = {} , time_dfs[MAXLOG + 2] = {};
	LL val[MAXLOG + 2][N + 2] = {};
	bool used[N + 2] = {};
	int n , q;
	
	vector<int>ke[N + 2];
		void add_canh(int u , int v , int id){
			ke[u].push_back(id) , ke[v].push_back(id);
			return;
		}
	
		class IT{
		public:
			vector<LL> open;
			vector<LL> st , lazy;
			
			void load_size(int n){
				st = lazy = vector<LL>(n * 4 + 2 , 0);
				open = vector<LL>(n * 4 + 2 , inf);
				return;
			}
			
			void build(int dep , int id , int l , int r){
				if (l == r) st[id] = val[dep][l]; 
				else{
					int m = (l + r) / 2;
					build(dep , id * 2 , l , m);
					build(dep , id * 2 + 1 , m + 1 , r);
					st[id] = min(st[id * 2] , st[id * 2 + 1]);
				}
				return;
			}
			
			void pushdown(int id){
				LL &t = lazy[id];
					st[id * 2] += t , lazy[id * 2] += t;
					st[id * 2 + 1] += t , lazy[id * 2 + 1] += t;
					
					if (open[id * 2] != inf) open[id * 2] += t;
					if (open[id * 2 + 1] != inf) open[id * 2 + 1] += t;
				t = 0;
				return;
			}
			
			void upd(int id , int l , int r , int u , int v , LL val){
				if (l > v || r < u) return ;
				if (u <= l && r <= v){
					st[id] += val;
					lazy[id] += val;
					if (open[id] != inf) open[id] += val;
					return;
				}
				int m = (l + r) / 2;
				pushdown(id);
				upd(id * 2 , l , m , u , v , val);
				upd(id * 2 + 1 , m + 1 , r , u , v , val);
				st[id] = min(st[id * 2] , st[id * 2 + 1]);
				open[id] = min(open[id * 2] , open[id * 2 + 1]);
				return;
			}
			
			void soak(int id , int l , int r , int pos , bool val){
				if (l == r){
					if (val == 0) open[id] = inf; else open[id] = st[id];
					return;
				}
				else {
					int m = (l + r) / 2;
					pushdown(id);
					if (pos <= m) soak(id * 2 , l , m , pos , val);
						else soak(id * 2 + 1 , m + 1 , r , pos , val);
					open[id] = min(open[id * 2] , open[id * 2 + 1]);
					st[id] = min(st[id * 2] , st[id * 2 + 1]);
				}
				return;
			}
			
			LL Get_dist(int id , int l , int r, int u , int v){
				if (l > v || r < u) return inf;
				if (u <= l && r <= v) return open[id];
				int m = (l + r) / 2;
				pushdown(id);
				return min(Get_dist(id * 2 , l , m , u , v) , Get_dist(id * 2 + 1 , m + 1 , r , u , v));
			}
			
			LL Get(int id , int l , int r , int pos){
				if (l == r) return st[id];
				else{
					int m = (l + r) / 2;
					pushdown(id);
					if (pos <= m) return Get(id * 2 , l , m , pos);
					return Get(id * 2 + 1 , m + 1 , r , pos);
				}
			}
	};
		
		IT st[MAXLOG + 2];
namespace Centroid{
	int sub[N + 2] = {};
	bool del[N + 2] = {};
		
		void dfs_size(int u, int p){
			sub[u] = 1;
			for(int id : ke[u]){
				int v = u ^ x[id] ^ y[id];
				if (del[v] || v == p) continue;
				dfs_size(v , u);
				sub[u] += sub[v];
			}
			return;
		}
		
		int Find_centroid(int u , int p , int half){
			for(int id : ke[u]){
				int v = u ^ x[id] ^ y[id];
				if (v == p || del[v]) continue;
				if (sub[v] > half) return Find_centroid(v , u , half);
			}
			return u;
		}
		
	int dep[N + 2] = {} , par[N + 2] = {};
	
	
		void dfs(int dep , int u , int p , LL sum = 0){
			sta[dep][u] = ++time_dfs[dep];
			val[dep][time_dfs[dep]] = sum;
						
			for(int id : ke[u]){
				int v = u ^ x[id] ^ y[id];
				if (v == p || del[v]) continue;
				dfs(dep , v , u , sum + w[id]);
			}
			fin[dep][u] = time_dfs[dep];
			return;
		}
		
	void build(int u , int p){
		dfs_size(u,u);
		u = Find_centroid(u , u , sub[u] / 2);
	
		del[u] = true;
			par[u] = p;
			dep[u] = dep[p] + 1;	
			
			dfs(dep[u] , u , u);
			
		for(int id : ke[u]){
			int v = u ^ x[id] ^ y[id];
			if (del[v]) continue;
			build(v , u);
		}
		return;
	}
	
	bool is_ancestor(int dep , int u , int v){
		return sta[dep][u] <= sta[dep][v] && sta[dep][v] <= fin[dep][u];
	}
}
using namespace Centroid;

	void annual(int u , int v,  LL cost){
		for(int i = min(dep[u] , dep[v]); i >= 1; --i){
			if (is_ancestor(i , u  , v)  == false) swap(u , v);
			// u -> ancestor , v -> children
				st[i].upd(1 , 1 , time_dfs[i] , sta[i][v] , fin[i][v] , cost);
		}
		return;
	}
	
	void soak(int u){
		used[u] = !used[u];
		for(int i = dep[u] ; i >= 1; --i){
			st[i].soak(1 , 1 , time_dfs[i] , sta[i][u] , used[u]);
		}
		return;
	}
	
	LL seek(int u){
		LL ans = inf;
		int cur = u;
		for(int i = dep[u] ; i >= 1; --i , cur = par[cur]){
			LL dist_u = st[i].Get(1 , 1 , time_dfs[i] , sta[i][u]) + st[i].Get_dist(1 , 1 , time_dfs[i] , sta[i][cur] , fin[i][cur]);
//			cout << cur << ' ' << dist_u << ' ' << st[i].Get(1 , 1 , time_dfs[i], sta[i][])
 			minimize(ans , dist_u);
		}
		return ans;
	}
	
map<pair<int,int> , int> mp;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}	
			
		cin >> n >> q;
		FOR(i,1,n-1){
			cin >> x[i] >> y[i] >> w[i];
			if (x[i] > y[i]) swap(x[i] , y[i]);
			mp[{x[i] , y[i]}] = i;
			add_canh(x[i] , y[i] , i);
		}
		memset(val,0x3f,sizeof val);
		build(1,1);
		for(int i = 1; i <= MAXLOG; ++i){
			if (time_dfs[i] == 0) continue;
			st[i].load_size(time_dfs[i]);
			st[i].build(i,1,1,time_dfs[i]);
		}
		while (q--){
			int t; cin >> t;
			if (t == 2) {
				int u; cin >> u;
				soak(u);
			}
			if (t == 1){
				int u; cin >> u;
				cout << seek(u) << '\n';	
			}
			if (t == 3){
				int u , v , new_w; cin >> u >> v >> new_w;
				if (u > v) swap(u , v);
				int id = mp[{u , v}];
				LL cost = new_w - w[id];
				w[id] += cost;
				annual(u , v , cost);
			}
		}
	return 0;
}

Compilation message (stderr)

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

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