Submission #712315

#	Time	Username	Problem	Language	Result	Execution time	Memory
712315		yuseok0803	Traffickers (RMI18_traffickers)	C++14	100 / 100	3146 ms	72368 KiB

traffickers

#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 (stderr)

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++)
      |                ~^~~~~~~~~
traffickers.cpp: In function 'void dfs2(int, int)':
traffickers.cpp:68:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |  for (auto [t0, r, i, val] : Qs_U[u]) d[t0][r].up(i, val);
      |            ^
traffickers.cpp:69:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |  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++)
      |            ^
traffickers.cpp:72:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |  for (auto [t0, r, i, val] : Qs_U[u]) d[t0][r].up(i, -val);
      |            ^

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