Submission #696361

#	Time	Username	Problem	Language	Result	Execution time	Memory
696361		sugartheanh	Traffickers (RMI18_traffickers)	C++14	0 / 100	1 ms	1492 KiB

traffickers

#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(){
    freopen("new.inp","r",stdin);
    freopen("new.out","w",stdout);
		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);
                cout<<nod<<' '<<rest<<' '<<lenght<<'\n';
				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 (stderr)

traffickers.cpp: In function 'int main()':
traffickers.cpp:158:9: warning: unused variable 'l' [-Wunused-variable]
  158 |     int l = lca(a,b);
      |         ^
traffickers.cpp:80:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     freopen("new.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:81:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     freopen("new.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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