Submission #1295511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295511		jahongir	Traffickers (RMI18_traffickers)	C++17	100 / 100	757 ms	31244 KiB

traffickers

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define all(a) a.begin(),a.end()



const int mxn = 3e4+1, mxd = 20, lg2 = 15;
vector<int> g[mxn];
int tin[mxn],tout[mxn],tim=-1;
int dep[mxn],suc[mxn][lg2];
int bit[mxd][mxd][mxn];


void add(int i, int i1, int i2, int val){
	for(i1--; i <= mxn; i+=i&-i)
		bit[i1][i2][i] += val;
}

int get(int i, int i1, int i2){
	int res = 0;
	for(i1--; i > 0; i-=i&-i)
		res += bit[i1][i2][i];
	return res;
}


void dfs(int u, int p){
	tin[u] = ++tim;
	for(int i = 1; i < lg2; i++)
		suc[u][i] = suc[suc[u][i-1]][i-1];
	for(auto v : g[u])if(v!=p){
		dep[v] = dep[u]+1;
		suc[v][0] = u;
		dfs(v,u);
	}
	tout[u] = tim;
}

bool is_anc(int u, int v){
	return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int get_lca(int u, int v){
	if(is_anc(u,v)) return u;
	if(is_anc(v,u)) return v;
	for(int i = lg2-1; i >= 0; i--)
		if(!is_anc(suc[u][i],v))
			u = suc[u][i];
	return suc[u][0];
}

void update(int u, int v, int val){
	int lca = u;
	for(; !is_anc(lca,v); lca = suc[lca][0]);
	int len = dep[u] + dep[v] - 2*dep[lca] + 1;
	for(int i = 0; ; i++, u = suc[u][0]){
		add(tin[u],len,i,val);
		add(tout[u]+1,len,i,-val);
		if(u==lca) break;
	}
	for(int i = len-1; v != lca; i--, v = suc[v][0]){
		add(tin[v],len,i,val);
		add(tout[v]+1,len,i,-val);
	}
}



ll query(int u, int t){
	if(t==-1) return 0ll;
	ll res = 0;
		
	for(int d = 1; d <= mxd; d++){
		ll sum1 = 0, sum2 = 0;
		for(int i = 0; i < d; i++){
			sum1 += get(tin[u],d,i);
			if(t%d >= i) sum2 += get(tin[u],d,i);
		}
		res += sum1 * (t/d) + sum2;
	}
	
	return res;
}


void solve(){
	int n,k,q; cin >> n;
	for(int i = 1; i < n; i++){
		int u,v; cin >> u >> v;
		g[u].pb(v); g[v].pb(u);
	}
	g[0].pb(1); dfs(0,-1);
	
	cin >> k;
	for(int i = 0; i < k; i++){
		int u,v; cin >> u >> v;
		update(u,v,1);
	}
	
	
	cin >> q;
	for(int i = 0; i < q; i++){
		int t; cin >> t;
		if(t==3){
			int u,v,t1,t2; cin >> u >> v >> t1 >> t2;
			int lca = get_lca(u,v);
			ll sum = query(u,t2) - query(u,t1-1);
			sum += query(v,t2) - query(v,t1-1);
			sum -= query(lca,t2) - query(lca,t1-1);
			sum -= query(suc[lca][0],t2) - query(suc[lca][0],t1-1);
			cout << sum << '\n';
		}else{
			int u,v; cin >> u >> v;
			update(u,v,3-2*t);
		}
	}

}
 
 
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int t = 1;
//	cin >> t;
	for(int i = 0; i < t; i++){solve();}
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40