oj.uz

Submission #589065

# Submission time Handle Problem Language Result Execution time Memory
589065 2022-07-04T09:07:20 Z Red_Inside Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 75980 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;
}
 
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)
{
	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();
	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, (int)(ancs.size()))
			{
				int b = (d + a) / 2;
				if(ancs.size() > b)
					update(ancs[b], w, b - a);
				else
					update(ancs.back(), w, (int)ancs.size() - 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:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main()
      | ^~~~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:132:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  132 |     if(ancs.size() > b)
      |        ~~~~~~~~~~~~^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14392 KB Output is correct
2 Correct 7 ms 14460 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Incorrect 9 ms 14676 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 499 ms 57248 KB Output is correct
3 Correct 879 ms 54008 KB Output is correct
4 Correct 438 ms 67352 KB Output is correct
5 Correct 600 ms 55740 KB Output is correct
6 Correct 693 ms 55012 KB Output is correct
7 Correct 711 ms 55256 KB Output is correct
8 Correct 573 ms 55460 KB Output is correct
9 Correct 386 ms 75980 KB Output is correct
10 Correct 561 ms 71132 KB Output is correct
11 Incorrect 494 ms 57176 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 499 ms 57248 KB Output is correct
3 Correct 879 ms 54008 KB Output is correct
4 Correct 438 ms 67352 KB Output is correct
5 Correct 600 ms 55740 KB Output is correct
6 Correct 693 ms 55012 KB Output is correct
7 Correct 711 ms 55256 KB Output is correct
8 Correct 573 ms 55460 KB Output is correct
9 Correct 386 ms 75980 KB Output is correct
10 Correct 561 ms 71132 KB Output is correct
11 Incorrect 494 ms 57176 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 665 ms 72932 KB Output is correct
3 Correct 2609 ms 67200 KB Output is correct
4 Correct 1089 ms 68488 KB Output is correct
5 Correct 3494 ms 54028 KB Output is correct
6 Correct 2028 ms 53440 KB Output is correct
7 Correct 1160 ms 53652 KB Output is correct
8 Correct 439 ms 53968 KB Output is correct
9 Correct 638 ms 66936 KB Output is correct
10 Correct 2541 ms 70480 KB Output is correct
11 Correct 1628 ms 54416 KB Output is correct
12 Execution timed out 4073 ms 53652 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14392 KB Output is correct
2 Correct 7 ms 14460 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Incorrect 9 ms 14676 KB Output isn't correct
5 Halted 0 ms 0 KB -