oj.uz

답안 #330864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
330864 2020-11-26T19:16:15 Z Knps4422 Traffickers (RMI18_traffickers) C++14
0 / 100
 3500 ms 336620 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){
							cout << a << ' ' << b << ' ' << i << ' ' << j << ' ' << gt << '\n';
						}
						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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 2028 KB Output isn't correct
2 Incorrect 77 ms 11116 KB Output isn't correct
3 Incorrect 69 ms 10348 KB Output isn't correct

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 719 ms 96492 KB Output isn't correct
2 Incorrect 762 ms 86252 KB Output isn't correct
3 Incorrect 622 ms 94956 KB Output isn't correct
4 Incorrect 696 ms 95756 KB Output isn't correct
5 Incorrect 747 ms 93380 KB Output isn't correct
6 Incorrect 741 ms 94700 KB Output isn't correct
7 Incorrect 713 ms 94444 KB Output isn't correct
8 Incorrect 679 ms 98900 KB Output isn't correct
9 Incorrect 772 ms 99820 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3587 ms 326780 KB Time limit exceeded
2 Execution timed out 3614 ms 336620 KB Time limit exceeded
3 Execution timed out 3577 ms 329968 KB Time limit exceeded
4 Execution timed out 3596 ms 315544 KB Time limit exceeded
5 Execution timed out 3552 ms 307844 KB Time limit exceeded
6 Execution timed out 3609 ms 334608 KB Time limit exceeded
7 Execution timed out 3602 ms 323908 KB Time limit exceeded
8 Execution timed out 3612 ms 324608 KB Time limit exceeded