답안 #659559

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
659559 2022-11-18T13:56:49 Z NekoRolly Traffickers (RMI18_traffickers) C++17
100 / 100
3085 ms 72100 KB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e4+4;
const int N1 = 5e4+4;

struct Bit{
	int n,t[N1];

	void up(int i,int val){
		for (; i<=n; i+=i&-i) t[i] += val;
	}

	int que(int l,int r){ int ans = 0;
		for (; r>0; r-=r&-r) ans += t[r];
		for (l--; l>0; l-=l&-l) ans -= t[l];
		return ans;
	}
} d[20][21];

struct Update{
	int t0,r,i,val;
};

struct Query{
	int T,i,id,val;
};

int n,n1,n2,k,q;
vector<int> adj[N];
int L[N],R[N],up[N][15];

vector<Update> Qs_U[N];
vector<Query> Qs_Q[N];
ll ans[N1];

void dfs1(int u,int p){ L[u] = n1++, up[u][0] = p;
	for (int i=1; i<15; i++) up[u][i] = up[up[u][i-1]][i-1];
	for (int v : adj[u]) if (v != p) dfs1(v, u);
	R[u] = n1;
}

bool isa(int a,int b){
	return L[a] <= L[b] && R[b] <= R[a];
}

int lca(int a,int b){
	if (isa(a, b)) return a;
	if (isa(b, a)) return b;
	for (int i=14; i>=0; i--)
		if (!isa(up[a][i], b)) a = up[a][i];
	return up[a][0];
}

void add(int a,int b,int id,int val){ vector<int> aux,v;
	int l = lca(a, b);
	for (; ; a=up[a][0]){ v.push_back(a);
		if (a == l) break;
	}
	for (; b!=l; b=up[b][0]) aux.push_back(b);
	reverse(aux.begin(), aux.end());
	for (int x : aux) v.push_back(x);
	for (int i=0; i<v.size(); i++)
		Qs_U[v[i]].push_back({i, int(v.size()), id, val});
}

void dfs2(int u,int p){ 
	for (auto [t0, r, i, val] : Qs_U[u]) d[t0][r].up(i, val);
	for (auto [T, i, id, val] : Qs_Q[u]) for (int t0=0; t0<=min(19, T); t0++) for (int r=1; r<=20; r++)
		ans[id] += 1ll*val*d[t0][r].que(1, i)*((T-t0)/r + 1);
	for (int v : adj[u]) if (v != p) dfs2(v, u);
	for (auto [t0, r, i, val] : Qs_U[u]) d[t0][r].up(i, -val);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;

	for (int i=1,a,b; i<n; i++){ cin >> a >> b;
		adj[a].push_back(b), adj[b].push_back(a);
	}

	dfs1(1, 1);

	cin >> k;

	for (int a,b; k--; ){ cin >> a >> b; add(a, b, 1, 1);}

	cin >> q; q++;
	for (int t,a,b,t1,t2,i=2; i<=q; i++){ cin >> t >> a >> b;
		if (t == 3){ cin >> t1 >> t2; 
			int l = lca(a, b);
			if (t1){
				Qs_Q[a].push_back({t1-1, i, n2, -1});
				Qs_Q[b].push_back({t1-1, i, n2, -1});
				Qs_Q[l].push_back({t1-1, i, n2, 1});
				if (l != 1) Qs_Q[up[l][0]].push_back({t1-1, i, n2, 1});
			}
			Qs_Q[a].push_back({t2, i, n2, 1});
			Qs_Q[b].push_back({t2, i, n2, 1});
			Qs_Q[l].push_back({t2, i, n2, -1});
			if (l != 1) Qs_Q[up[l][0]].push_back({t2, i, n2, -1});
			n2++;
		}
		else add(a, b, i, t==1 ? 1 : -1);
	}

	for (int t0=0; t0<20; t0++) for (int r=1; r<=20; r++) d[t0][r].n = q;

	dfs2(1, -1);

	for (int i=0; i<n2; i++) cout << ans[i] << "\n";

	return 0;
}

Compilation message

traffickers.cpp: In function 'void add(int, int, int, int)':
traffickers.cpp:63:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for (int i=0; i<v.size(); i++)
      |                ~^~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 6 ms 4956 KB Output is correct
3 Correct 7 ms 4828 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 11896 KB Output is correct
2 Correct 141 ms 11528 KB Output is correct
3 Correct 149 ms 12436 KB Output is correct
4 Correct 159 ms 12224 KB Output is correct
5 Correct 155 ms 11736 KB Output is correct
6 Correct 146 ms 11900 KB Output is correct
7 Correct 146 ms 11880 KB Output is correct
8 Correct 159 ms 12140 KB Output is correct
9 Correct 148 ms 12236 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2877 ms 70804 KB Output is correct
2 Correct 3014 ms 72100 KB Output is correct
3 Correct 2643 ms 70720 KB Output is correct
4 Correct 2813 ms 69776 KB Output is correct
5 Correct 3085 ms 68340 KB Output is correct
6 Correct 2741 ms 71728 KB Output is correct
7 Correct 2304 ms 71696 KB Output is correct
8 Correct 2334 ms 71060 KB Output is correct