Submission #966400

#	Time	Username	Problem	Language	Result	Execution time	Memory
966400		Alkaser_ID	Sprinkler (JOI22_sprinkler)	C++17	12 / 100	1320 ms	99432 KiB

sprinkler

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
const ll N = 5e5 + 5;

ll n, mod;
vector<ll> adj[N], str[N];
ll a[N], b[N], c[N], par[N]; pair<ll, ll> ch[N], sch[N];
ll seg[10 * N], lazy[10 * N];
inline void dfs() {
	b[1] = 1; c[1] = 1;
	queue<pair<ll, ll>> q;
	ll timer = 2;
	for (ll j = 0; j < str[1].size(); ++j) q.push({ str[1][j],1 });
	for (; !q.empty();) {
		pair<ll, ll> p = q.front(); q.pop();
		ll i = p.first, pr = p.second;
		par[i] = pr;
		b[i] = timer; c[timer] = i;
		++timer;
		for (ll j = 0; j < str[i].size(); ++j) {
			if (str[i][j] == pr) continue;
			q.push({ str[i][j],i });
		}
	}
}
inline void convert() {
	for (ll i = 1; i <= n; ++i) {
		for (ll j = 0; j < str[i].size(); ++j) {
			adj[b[i]].push_back(b[str[i][j]]);
		}
	}
}
inline void dfs1(ll i,ll pr) {
	par[i] = pr;
	ch[i] = { 1e9,0 };
	for (ll j = 0; j < adj[i].size(); ++j) {
		if (adj[i][j] == par[i]) continue;
		dfs1(adj[i][j], i);
		ch[i].first = min(ch[i].first, adj[i][j]);
		ch[i].second = max(ch[i].second, adj[i][j]);
	}
	if (ch[i].first == 1e9) ch[i] = { -1,-1 };
}
inline void dfs2(ll i) {
	pair<ll, ll>& p = sch[i]; pair<ll, ll> org = { 1e9,0 };
	p = { 1e9,0 };
	for (ll j = 0; j < adj[i].size(); ++j) {
		if (adj[i][j] == par[i]) continue;
		if (ch[adj[i][j]].first == -1) continue;
		p.first = min(p.first, ch[adj[i][j]].first);
		p.second = max(p.second, ch[adj[i][j]].second);
	}
	if (p == org) p = { -1,-1 };
}
inline void upd(ll node, bool bl) {
	ll k = lazy[node];
	seg[node] = (seg[node] * k) % mod;
	if (!bl) {
		lazy[node * 2] = lazy[node * 2] * k % mod;
		lazy[node * 2 + 1] = lazy[node * 2 + 1] * k % mod;
	}
	lazy[node] = 1;
}
inline void build(ll node, ll l, ll r) {
	lazy[node] = 1;
	if (l == r) {
		seg[node] = a[l];
		return;
	}
	ll mid = (l + r) / 2;
	build(node * 2, l, mid);
	build(node * 2 + 1, mid + 1, r);
	seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
}
inline void update(ll node, ll l, ll r, ll lx, ll rx, ll vl) {
	upd(node, (l == r));
	if (l >= lx && r <= rx) {
		if (l == r) {
			seg[node] = (seg[node] * vl) % mod;
		}
		else lazy[node] = (lazy[node] * vl) % mod;
		return;
	}
	if (l > rx || r < lx) return;
	ll mid = (l + r) / 2;
	update(node * 2, l, mid, lx, rx, vl);
	update(node * 2 + 1, mid + 1, r, lx, rx, vl);
	seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
}
inline ll get(ll node, ll l, ll r, ll ind) {
	upd(node, (l == r));
	if (l == r) return seg[node];
	ll mid = (l + r) / 2;
	if (ind <= mid)
		return get(node * 2, l, mid, ind);
	return get(node * 2 + 1, mid + 1, r, ind);
}
inline void update_dfs(ll i, ll vl, ll d, ll pr) {
	a[i] = (a[i] * vl) % mod;
	if (d == 0) return;
	for (ll j = 0; j < adj[i].size(); ++j) {
		if (adj[i][j] == pr) continue;
		update_dfs(adj[i][j], vl, d - 1, i);
	}
}
int main()
{
	cin >> n >> mod;
	for (ll i = 1; i < n; ++i) {
		ll u, v; cin >> u >> v;
		str[u].push_back(v);
		str[v].push_back(u);
	}
	for (ll i = 1; i <= n; ++i) cin >> a[i];
	vector<ll> cp(n + 3);
	for (ll i = 1; i <= n; ++i) cp[i] = a[i];
	dfs();
	convert();
	dfs1(1, 0);
	dfs2(1);
	for (ll i = 1; i <= n; ++i) a[i] = cp[c[i]];
	build(1, 1, n);
	ll q; cin >> q;
	vector<ll> ans;
	for (ll cn = 0; cn < q; ++cn) {
		ll tp; cin >> tp;
		if (tp == 1) {
			ll nd, d, w; cin >> nd >> d >> w;
			nd = b[nd];
			if (n <= 1000 && q <= 1000) {
				update_dfs(nd, w, d, nd);
			}
			if (d == 0) {
				update(1, 1, n, nd, nd, w);
			}
			else if (d == 1) {
				update(1, 1, n, nd, nd, w);
				update(1, 1, n, par[nd], par[nd], w);
				if (ch[nd].first != -1)
					update(1, 1, n, ch[nd].first, ch[nd].second, w);
			}
			else if(d == 2) {
				ll pr = par[nd];
				if (par[pr] != 0)
					update(1, 1, n, par[pr], par[pr], w);
				if (pr != 0) 
					update(1, 1, n, pr, pr, w);
				update(1, 1, n, ch[pr].first, ch[pr].second, w);
				if(ch[nd].first != -1)
					update(1, 1, n, ch[nd].first, ch[nd].second, w);
				if(sch[nd].first != -1)
					update(1, 1, n, sch[nd].first, sch[nd].second, w);
			}
		}
		else {
			ll ind; cin >> ind;
			ind = b[ind];
			if (n <= 1000 && q <= 1000) {
				cout << a[ind] << '\n';
				ans.push_back(a[ind]);
			}
			else {
				ll res = get(1, 1, n, ind);
				cout << res << '\n';
				ans.push_back(res);
			}
		}
	}
}

Compilation message (stderr)

sprinkler.cpp: In function 'void dfs()':
sprinkler.cpp:19:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for (ll j = 0; j < str[1].size(); ++j) q.push({ str[1][j],1 });
      |                 ~~^~~~~~~~~~~~~~~
sprinkler.cpp:26:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for (ll j = 0; j < str[i].size(); ++j) {
      |                  ~~^~~~~~~~~~~~~~~
sprinkler.cpp: In function 'void convert()':
sprinkler.cpp:34:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for (ll j = 0; j < str[i].size(); ++j) {
      |                  ~~^~~~~~~~~~~~~~~
sprinkler.cpp: In function 'void dfs1(ll, ll)':
sprinkler.cpp:42:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (ll j = 0; j < adj[i].size(); ++j) {
      |                 ~~^~~~~~~~~~~~~~~
sprinkler.cpp: In function 'void dfs2(ll)':
sprinkler.cpp:53:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for (ll j = 0; j < adj[i].size(); ++j) {
      |                 ~~^~~~~~~~~~~~~~~
sprinkler.cpp: In function 'void update_dfs(ll, ll, ll, ll)':
sprinkler.cpp:107:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for (ll j = 0; j < adj[i].size(); ++j) {
      |                 ~~^~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 9 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17