oj.uz

Submission #589143

# Submission time Handle Problem Language Result Execution time Memory
589143 2022-07-04T09:39:49 Z Red_Inside Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 60460 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+100,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];
int L, h[maxn];
vector <int> edge[maxn];
vector <pii> vec[maxn];
vector <int> 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;
}

inline void push(int v, int tn)
{
	if(t[tn][v] != 1)
	{
		t[tn][v * 2] = 1ll * t[tn][v * 2] * t[tn][v] % L;
		t[tn][v * 2 + 1] = 1ll * 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, int w, int tn)
{
	if(l <= tl && tr <= r)
	{
		t[tn][v] = (1ll * t[tn][v]) * (1ll * 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);
}

int 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);
}
 
inline void update(int x, int w, int d)
{
	if(d < 0) return;
	if(sz[deep[x] + d] == 0) return;
//	cout << "UPDATE " << x << " " << w << " " << d << " " << tin[x] << " " << tout[x] << endl;
//	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();
//	que[deep[x] + d].pb({{L, R}, w});
	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;
			int w;
			cin >> x >> d >> w;
			vector <int> ancs;
			int v = x;
			forn(0, iter, d)
			{
				ancs.pb(v);
				v = anc[v];
				if(v == 0) break;
			}
			forn(-d, a, d)
			{
				int b = (d + a) / 2;
				if((int)ancs.size() > b)
				{
//					cout << "START UPDATE " << ancs[b] << " " << a << " " << b << endl;
					update(ancs[b], w, b - a);
				}
				else
				{
//					cout << "START UPDATE " << ancs.back() << " " << a << " " << b << endl;
					update(ancs.back(), w, (int)ancs.size() - 1 - a);
				}
			}
		}
		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:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   96 | main()
      | ^~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14424 KB Output is correct
2 Correct 9 ms 14424 KB Output is correct
3 Correct 9 ms 14404 KB Output is correct
4 Incorrect 11 ms 14628 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Incorrect 452 ms 44628 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Incorrect 452 ms 44628 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14596 KB Output is correct
2 Correct 711 ms 60460 KB Output is correct
3 Correct 2530 ms 54728 KB Output is correct
4 Correct 1089 ms 56192 KB Output is correct
5 Correct 3556 ms 41712 KB Output is correct
6 Correct 2545 ms 41284 KB Output is correct
7 Correct 1412 ms 41472 KB Output is correct
8 Correct 449 ms 41692 KB Output is correct
9 Correct 852 ms 54664 KB Output is correct
10 Correct 2804 ms 58268 KB Output is correct
11 Correct 1660 ms 42620 KB Output is correct
12 Execution timed out 4010 ms 41472 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Incorrect 882 ms 56540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14424 KB Output is correct
2 Correct 9 ms 14424 KB Output is correct
3 Correct 9 ms 14404 KB Output is correct
4 Incorrect 11 ms 14628 KB Output isn't correct
5 Halted 0 ms 0 KB -