oj.uz

Submission #330865

# Submission time Handle Problem Language Result Execution time Memory
330865 2020-11-26T19:16:34 Z Knps4422 Traffickers (RMI18_traffickers) C++14
100 / 100
 2120 ms 256108 KB 
#include <bits/stdc++.h>
#define ll long long 
#define vec vector
#define pb push_back
const int nmax = 50005;

using namespace std;

int n, k, q;
vec < int > g[nmax];
int depth[nmax], tin[nmax], tout[nmax], par[nmax][21];
int timer;

void dfs(int nod , int p){
	depth[nod] = depth[p] + 1;
	par[nod][0] = p;
	tin[nod] = ++timer;
	for(int j : g[nod]){
		if(j == p)continue;
		dfs(j,nod);
	}
	tout[nod] = ++timer;
}

long long fw[2*nmax][23][23];

int lca(int x ,int y){
	if(x == y)return x;
	if(depth[x] < depth[y])swap(x,y);
	if(tin[x] > tin[y] && tout[x] < tout[y])return y;
	for(int i = 20 ; i >= 0 ; i--){
		int nd = par[x][i];
		if(tin[nd] < tin[y] && tout[nd] > tout[y])continue;
		x = nd;
	}
	return par[x][0];
}


void update( int nod , int rest , int lenght , int val){
	int x = tin[nod];
	while(x <= timer){
		fw[x][lenght][rest] += val;
		x += x&-x;
	}
	x = tout[nod];
	while(x <= timer){
		fw[x][lenght][rest] -= val;
		x += x&-x;
	}
}

long long get( int nod1 , int nod2 , int lenght , int rest){
	int l = lca(nod1,nod2);
	int x = tin[nod2];
	ll rs = 0;
	while(x > 0){
		rs += fw[x][lenght][rest];
		x -= x&-x;
	}
	x = tin[nod1];
	while(x > 0){
		rs += fw[x][lenght][rest];
		x -= x&-x;
	}
	x = tin[l];
	while(x > 0){
		rs -= fw[x][lenght][rest];
		x -= x&-x;
	}
	x = tin[l] - 1;
	while(x > 0){
		rs -= fw[x][lenght][rest];
		x -= x&-x;
	}
	return rs;
}


int main(){
		cin >> n;
		for(int i = 1 ; i < n ; i++){
			int a, b;
			cin >> a >> b;
			g[a].pb(b);
			g[b].pb(a);
		}
		dfs(1,0);
		for(int j = 1; (1<<j) <= n; j++){
			for(int i = 1 ; i <= n ; i++){
				par[i][j] = par[par[i][j-1]][j-1];
			}
		}
		tout[0] = timer + 1;
		cin >> k;
		for(int i = 1; i <= k; i++){
			int a, b;
			cin >> a >> b;
			int l = lca(a,b);
			int lenght = depth[a] + depth[b] - 2 * depth[l] + 1;
			int nod = a, rest = 0;
			while(nod != l){
				update(nod,rest,lenght,1);
				nod = par[nod][0];
				++rest;
			}
			nod = b , rest = lenght - 1;
			while(nod != l){
				update(nod,rest,lenght,1);
				nod = par[nod][0];
				--rest;
			}
			update(nod,rest,lenght,1);
		}
		cin >> q;
		for(int ii = 0 ; ii < q ; ii++){
			int type, a, b;
			cin >> type >> a >> b;
			if(type == 1){
				int l = lca(a,b);
				int lenght = depth[a] + depth[b] - 2 * depth[l] + 1;
				int nod = a, rest = 0;
				while(nod != l){
					update(nod,rest,lenght,1);
					nod = par[nod][0];
					++rest;
				}
				nod = b , rest = lenght - 1;
				while(nod != l){
					update(nod,rest,lenght,1);
					nod = par[nod][0];
					--rest;
				}
				update(nod,rest,lenght,1);
			}
			if(type == 2){
				int l = lca(a,b);
				int lenght = depth[a] + depth[b] - 2 * depth[l] + 1;
				int nod = a, rest = 0;
				while(nod != l){
					update(nod,rest,lenght,-1);
					nod = par[nod][0];
					++rest;
				}
				nod = b , rest = lenght - 1;
				while(nod != l){
					update(nod,rest,lenght,-1);
					nod = par[nod][0];
					--rest;
				}
				update(nod,rest,lenght,-1);
			}
			if(type == 3){
				long long t1 , t2;
				cin >> t1 >> t2;
				int l = lca(a,b);
				if(tin[a] > tin[b])swap(a,b);
				ll rez = 0;
				t1--;
				for(int i = 1; i <= 20 ; i++){
					for(int j = 0 ; j < i ; j++){
						ll gt = get(a,b,i,j);
						if(gt != 0){
						}
						rez += get(a,b,i,j)*(t2/i + (t2%i>=j ? 1 : 0) - t1/i - (t1%i>=j ? 1 : 0));
					}
				}
				cout << rez << '\n';
			}
		}
}

Compilation message

traffickers.cpp: In function 'int main()':
traffickers.cpp:156:9: warning: unused variable 'l' [-Wunused-variable]
  156 |     int l = lca(a,b);
      |         ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1900 KB Output is correct
2 Correct 24 ms 9964 KB Output is correct
3 Correct 18 ms 9324 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 82732 KB Output is correct
2 Correct 207 ms 72684 KB Output is correct
3 Correct 140 ms 81260 KB Output is correct
4 Correct 179 ms 82156 KB Output is correct
5 Correct 201 ms 80108 KB Output is correct
6 Correct 191 ms 81132 KB Output is correct
7 Correct 182 ms 80620 KB Output is correct
8 Correct 181 ms 85356 KB Output is correct
9 Correct 222 ms 85868 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1706 ms 254648 KB Output is correct
2 Correct 1376 ms 255724 KB Output is correct
3 Correct 1501 ms 255384 KB Output is correct
4 Correct 1974 ms 250864 KB Output is correct
5 Correct 2120 ms 246944 KB Output is correct
6 Correct 1383 ms 255468 KB Output is correct
7 Correct 1922 ms 256016 KB Output is correct
8 Correct 1929 ms 256108 KB Output is correct