oj.uz

Submission #588833

# Submission time Handle Problem Language Result Execution time Memory
588833 2022-07-04T06:19:12 Z Red_Inside Sprinkler (JOI22_sprinkler) C++17
0 / 100
 834 ms 81080 KB 
//
#include <bits/stdc++.h>

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define sortv(vv) sort(vv.begin(), vv.end())
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

using namespace std;
const int maxn=2e5+10,LOG=17, mod=1e9+7;
int block = 320, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bt(i) (1 << (i))
//#define int ll
const int inf=1e9+10;
#define y1 yy
#define prev pre
#define pii pair <int, int>

int n, q, anc[maxn], tin[maxn], tout[maxn], deep[maxn], sz[maxn];
ll L, h[maxn];
vector <int> edge[maxn];
vector <pii> vec[maxn];
vector <ll> t[maxn];

void dfs(int v, int pred = -1)
{
	tin[v] = ++timer;
	vec[deep[v]].pb({tin[v], v});
	for(auto to : edge[v])
	{
		if(to == pred) continue;
		deep[to] = deep[v] + 1;
		anc[to] = v;
		dfs(to, v);
	}
	tout[v] = timer;
}

void push(int v, int tn)
{
	t[tn][v * 2] = t[tn][v * 2] * t[tn][v] % L;
	t[tn][v * 2 + 1] = t[tn][v * 2 + 1] * t[tn][v] % L;
	t[tn][v] = 1;
}

void upd(int v, int tl, int tr, int l, int r, ll w, int tn)
{
	if(l <= tl && tr <= r)
	{
		t[tn][v] = t[tn][v] * w % L;
		return;
	}
	if(l > tr || r < tl) return;
	push(v, tn);
	upd(v * 2, tl, (tl + tr) / 2, l, r, w, tn);
	upd(v * 2 + 1, (tl + tr) / 2 + 1, tr, l, r, w, tn);
}

ll get(int v, int tl, int tr, int pos, int tn)
{
	if(tl == tr) return t[tn][v];
	push(v, tn);
	if(pos <= (tl + tr) / 2) return get(v * 2, tl, (tl + tr) / 2, pos, tn);
	return get(v * 2 + 1, (tl + tr) / 2 + 1, tr, pos, tn);
}

void update(int x, ll w, int d)
{
//	cout << "VECTOR\n";
//	for(auto i : vec[deep[x] + d]) cout << "   " << i.f << " " << i.s << endl;
	int L = lower_bound(all(vec[deep[x] + d]), mp(tin[x], 0)) - vec[deep[x] + d].begin() + 1;
	int R = upper_bound(all(vec[deep[x] + d]), mp(tout[x], inf)) - vec[deep[x] + d].begin();
	upd(1, 1, sz[deep[x] + d], L, R, w, deep[x] + d);
}

main()
{
	IOS
	cin >> n >> L;
	forn(1, i, n - 1)
	{
		int l, r;
		cin >> l >> r;
		edge[l].pb(r);
		edge[r].pb(l);
	}
	forn(1, i, n) cin >> h[i];
	deep[1] = 1;
	dfs(1);
	forn(1, i, n)
	{
		sz[i] = vec[i].size();
		t[i].assign(sz[i] * 4 + 10, 1);
//		build(1, 1, sz[i], i);
	}
	cin >> q;
	forn(1, i, q)
	{
		int ty;
		cin >> ty;
		if(ty == 1)
		{
			int x, d;
			ll w;
			cin >> x >> d >> w;
			if(d == 0)
			{
				h[x] = h[x] * w % L;
				continue;
			}
			if(d == 1)
			{
				h[x] = h[x] * w % L;
				if(anc[x] != 0)
				{
					h[anc[x]] = h[anc[x]] * w % L;
				}
				update(x, w, 1);
			}
			if(d == 2)
			{
				if(anc[x] != 0)
				{
					update(anc[x], w, 1);
					if(anc[anc[x]] != 0)
					{
						h[anc[anc[x]]] = h[anc[anc[x]]] * w % L;
					}
					h[anc[x]] = h[anc[x]] * w % L;
				}
				else
				{
					h[x] = h[x] * w % L;
				}
				update(x, w, 2);
				update(x, w, 1);
			}
		}
		else
		{
			int x;
			cin >> x;
			int pos = lower_bound(all(vec[deep[x]]), mp(tin[x], x)) - vec[deep[x]].begin() + 1;
			ll ans = h[x] * get(1, 1, sz[deep[x]], pos, deep[x]) % L;
//			cout << h[x] << " " << get(1, 1, sz[deep[x]], pos, deep[x]) << endl;
			cout << ans << "\n";
		}
	}
}

Compilation message

sprinkler.cpp:89:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   89 | main()
      | ^~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14408 KB Output is correct
2 Correct 439 ms 57564 KB Output is correct
3 Correct 722 ms 58828 KB Output is correct
4 Correct 484 ms 72392 KB Output is correct
5 Correct 479 ms 60788 KB Output is correct
6 Correct 507 ms 59948 KB Output is correct
7 Correct 480 ms 60208 KB Output is correct
8 Correct 480 ms 60508 KB Output is correct
9 Correct 724 ms 81080 KB Output is correct
10 Correct 834 ms 75912 KB Output is correct
11 Correct 465 ms 62036 KB Output is correct
12 Correct 542 ms 58712 KB Output is correct
13 Correct 364 ms 58752 KB Output is correct
14 Correct 443 ms 58680 KB Output is correct
15 Correct 436 ms 59020 KB Output is correct
16 Correct 466 ms 58628 KB Output is correct
17 Correct 516 ms 59196 KB Output is correct
18 Runtime error 26 ms 29016 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14408 KB Output is correct
2 Correct 439 ms 57564 KB Output is correct
3 Correct 722 ms 58828 KB Output is correct
4 Correct 484 ms 72392 KB Output is correct
5 Correct 479 ms 60788 KB Output is correct
6 Correct 507 ms 59948 KB Output is correct
7 Correct 480 ms 60208 KB Output is correct
8 Correct 480 ms 60508 KB Output is correct
9 Correct 724 ms 81080 KB Output is correct
10 Correct 834 ms 75912 KB Output is correct
11 Correct 465 ms 62036 KB Output is correct
12 Correct 542 ms 58712 KB Output is correct
13 Correct 364 ms 58752 KB Output is correct
14 Correct 443 ms 58680 KB Output is correct
15 Correct 436 ms 59020 KB Output is correct
16 Correct 466 ms 58628 KB Output is correct
17 Correct 516 ms 59196 KB Output is correct
18 Runtime error 26 ms 29016 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14352 KB Output is correct
2 Incorrect 403 ms 75696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 14420 KB Output isn't correct
2 Halted 0 ms 0 KB -