oj.uz

Submission #589112

# Submission time Handle Problem Language Result Execution time Memory
589112 2022-07-04T09:28:06 Z Red_Inside Sprinkler (JOI22_sprinkler) C++17
3 / 100
 4000 ms 76004 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];
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;
}

inline void push(int v, int tn)
{	
	if(t[tn][v] > 1)
	{
		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);
}
 
inline void update(int x, ll 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;
			ll 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(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()
      | ^~~~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:137:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  137 |     if(ancs.size() > b)
      |        ~~~~~~~~~~~~^~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 10 ms 14428 KB Output is correct
3 Correct 8 ms 14440 KB Output is correct
4 Correct 11 ms 14680 KB Output is correct
5 Correct 11 ms 14676 KB Output is correct
6 Correct 12 ms 14700 KB Output is correct
7 Correct 9 ms 14676 KB Output is correct
8 Correct 9 ms 14676 KB Output is correct
9 Correct 8 ms 14440 KB Output is correct
10 Correct 9 ms 14444 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 10 ms 14440 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 11 ms 14380 KB Output is correct
15 Correct 9 ms 14440 KB Output is correct
16 Correct 9 ms 14364 KB Output is correct
17 Correct 8 ms 14440 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 9 ms 14420 KB Output is correct
20 Correct 10 ms 14412 KB Output is correct
21 Correct 10 ms 14420 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 10 ms 14352 KB Output is correct
24 Correct 10 ms 14420 KB Output is correct
25 Correct 9 ms 14436 KB Output is correct
26 Correct 10 ms 14448 KB Output is correct
27 Correct 11 ms 14436 KB Output is correct
28 Correct 8 ms 14420 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 494 ms 57856 KB Output is correct
3 Correct 772 ms 54892 KB Output is correct
4 Correct 508 ms 67336 KB Output is correct
5 Correct 615 ms 55616 KB Output is correct
6 Correct 641 ms 54912 KB Output is correct
7 Correct 600 ms 55236 KB Output is correct
8 Correct 557 ms 55464 KB Output is correct
9 Correct 425 ms 76004 KB Output is correct
10 Correct 596 ms 71148 KB Output is correct
11 Correct 454 ms 57056 KB Output is correct
12 Correct 764 ms 54076 KB Output is correct
13 Correct 394 ms 54092 KB Output is correct
14 Correct 531 ms 53820 KB Output is correct
15 Incorrect 590 ms 54056 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 494 ms 57856 KB Output is correct
3 Correct 772 ms 54892 KB Output is correct
4 Correct 508 ms 67336 KB Output is correct
5 Correct 615 ms 55616 KB Output is correct
6 Correct 641 ms 54912 KB Output is correct
7 Correct 600 ms 55236 KB Output is correct
8 Correct 557 ms 55464 KB Output is correct
9 Correct 425 ms 76004 KB Output is correct
10 Correct 596 ms 71148 KB Output is correct
11 Correct 454 ms 57056 KB Output is correct
12 Correct 764 ms 54076 KB Output is correct
13 Correct 394 ms 54092 KB Output is correct
14 Correct 531 ms 53820 KB Output is correct
15 Incorrect 590 ms 54056 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 805 ms 68640 KB Output is correct
3 Correct 3462 ms 62460 KB Output is correct
4 Correct 1208 ms 66032 KB Output is correct
5 Execution timed out 4054 ms 55628 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 10 ms 14428 KB Output is correct
3 Correct 8 ms 14440 KB Output is correct
4 Correct 11 ms 14680 KB Output is correct
5 Correct 11 ms 14676 KB Output is correct
6 Correct 12 ms 14700 KB Output is correct
7 Correct 9 ms 14676 KB Output is correct
8 Correct 9 ms 14676 KB Output is correct
9 Correct 8 ms 14440 KB Output is correct
10 Correct 9 ms 14444 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 10 ms 14440 KB Output is correct
13 Correct 8 ms 14420 KB Output is correct
14 Correct 11 ms 14380 KB Output is correct
15 Correct 9 ms 14440 KB Output is correct
16 Correct 9 ms 14364 KB Output is correct
17 Correct 8 ms 14440 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 9 ms 14420 KB Output is correct
20 Correct 10 ms 14412 KB Output is correct
21 Correct 10 ms 14420 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 10 ms 14352 KB Output is correct
24 Correct 10 ms 14420 KB Output is correct
25 Correct 9 ms 14436 KB Output is correct
26 Correct 10 ms 14448 KB Output is correct
27 Correct 11 ms 14436 KB Output is correct
28 Correct 8 ms 14420 KB Output is correct
29 Correct 7 ms 14420 KB Output is correct
30 Correct 494 ms 57856 KB Output is correct
31 Correct 772 ms 54892 KB Output is correct
32 Correct 508 ms 67336 KB Output is correct
33 Correct 615 ms 55616 KB Output is correct
34 Correct 641 ms 54912 KB Output is correct
35 Correct 600 ms 55236 KB Output is correct
36 Correct 557 ms 55464 KB Output is correct
37 Correct 425 ms 76004 KB Output is correct
38 Correct 596 ms 71148 KB Output is correct
39 Correct 454 ms 57056 KB Output is correct
40 Correct 764 ms 54076 KB Output is correct
41 Correct 394 ms 54092 KB Output is correct
42 Correct 531 ms 53820 KB Output is correct
43 Incorrect 590 ms 54056 KB Output isn't correct
44 Halted 0 ms 0 KB -