oj.uz

Submission #671952

# Submission time Handle Problem Language Result Execution time Memory
671952 2022-12-14T10:21:21 Z Evirir Sprinkler (JOI22_sprinkler) C++17
9 / 100
 1565 ms 95412 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
//template<typename T>
//using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
ostream& operator<<(ostream &out, ii x){ out<<"("<<x.F<<","<<x.S<<")"; return out; }
template<typename T> void amax(T &a, T b){ a=max(a,b); }
template<typename T> void amin(T &a, T b){ a=min(a,b); }
const ll INF = ll(1e18);
ll MOD;

ll add(ll a, ll b, ll m = MOD)
{
	a+=b;
	if(abs(a)>=m) a%=m;
	if(a<0) a+=m;
	return a;
}
ll mult(ll a, ll b, ll m = MOD)
{
	if(abs(a)>=m) a%=m;
	if(abs(b)>=m) b%=m;
	a*=b;
	if(abs(a)>=m) a%=m;
	if(a<0) a+=m;
	return a;
}

const bool DEBUG = 0;
const int MAXN = 200005;
const int LG = 21;
const int MAXD = 41;

void dfs(int u, int p, const vector<vector<int>> &adj, vector<int> &prt)
{
	prt[u] = p;
	for (int v : adj[u])
	{
		if (v == p)
			continue;
		dfs(v, u, adj, prt);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n;
	vector<ll> h;
	vector<vector<int>> adj;
	vector<vector<ll>> depthProd;
	vector<int> prt;

	cin >> n >> MOD;
	adj.resize(n);
	h.resize(n);
	prt.resize(n, -1);
	depthProd.resize(n, vector<ll>(MAXD + 1, 1));
	forn(i,0,n-1)
	{
		int u,v; cin>>u>>v; u--; v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	forn(i, 0, n) cin >> h[i];

	dfs(0, -1, adj, prt);

	int Q;
	cin >> Q;
	while (Q--)
	{
		int t; cin>>t;
		if (t == 1)
		{
			int u, d;
			ll w;
			cin >> u >> d >> w;
			u--;
			for (int i = 0; i <= d; i++)
			{
				depthProd[u][d - i] = mult(depthProd[u][d - i], w);
				u = prt[u];
				if (u == -1)
					break;
			}
		}
		else
		{
			int u;
			cin >> u;
			u--;
			ll prod = h[u];
			for (int i = 0; i <= MAXD; i++)
			{
				if (i == MAXD || i == 0)
				{
					for (int j = i; j <= MAXD; j++)
						prod = mult(prod, depthProd[u][j]);
				}
				else
				{
					prod = mult(prod, depthProd[u][i]);
					if (i + 1 <= MAXD)
					{
						prod = mult(prod, depthProd[u][i + 1]);
					}
				}

				u = prt[u];
				if (u == -1)
					break;
			}
			cout << prod << '\n';
		}
	}

	return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 2 ms 724 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1140 ms 90788 KB Output is correct
3 Correct 432 ms 87604 KB Output is correct
4 Correct 979 ms 92176 KB Output is correct
5 Correct 790 ms 89176 KB Output is correct
6 Correct 479 ms 89180 KB Output is correct
7 Correct 431 ms 89548 KB Output is correct
8 Correct 316 ms 89856 KB Output is correct
9 Correct 1516 ms 95412 KB Output is correct
10 Correct 492 ms 91856 KB Output is correct
11 Correct 1110 ms 90744 KB Output is correct
12 Correct 445 ms 87676 KB Output is correct
13 Correct 247 ms 88256 KB Output is correct
14 Correct 252 ms 88244 KB Output is correct
15 Correct 248 ms 88228 KB Output is correct
16 Correct 261 ms 88112 KB Output is correct
17 Correct 263 ms 88628 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1140 ms 90788 KB Output is correct
3 Correct 432 ms 87604 KB Output is correct
4 Correct 979 ms 92176 KB Output is correct
5 Correct 790 ms 89176 KB Output is correct
6 Correct 479 ms 89180 KB Output is correct
7 Correct 431 ms 89548 KB Output is correct
8 Correct 316 ms 89856 KB Output is correct
9 Correct 1516 ms 95412 KB Output is correct
10 Correct 492 ms 91856 KB Output is correct
11 Correct 1110 ms 90744 KB Output is correct
12 Correct 445 ms 87676 KB Output is correct
13 Correct 247 ms 88256 KB Output is correct
14 Correct 252 ms 88244 KB Output is correct
15 Correct 248 ms 88228 KB Output is correct
16 Correct 261 ms 88112 KB Output is correct
17 Correct 263 ms 88628 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Incorrect 1095 ms 90864 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1513 ms 92672 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1565 ms 93784 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 2 ms 724 KB Output isn't correct
5 Halted 0 ms 0 KB -