oj.uz

Submission #892504

# Submission time Handle Problem Language Result Execution time Memory
892504 2023-12-25T12:42:54 Z vjudge1 Sprinkler (JOI22_sprinkler) C++17
12 / 100
 568 ms 113488 KB 
#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define mpa make_pair
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define bc back()
#define ar array
#define vll vector<ll> 
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;*/
template <class _T>
bool chmin(_T &x, const _T &y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag=false;
    if (x<y){
        x=y;flag|=true;
    }
    return flag;
}
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=2e18+7;
const ll mod=1e9+7;
const ll N=2e5+7;
const ld eps=1e-9;
vector<vll> g(N);
ll h[N];
ll i;
ll n,k,p[N];
ll val[N][50];
void dfs(ll v,ll p,ll w,ll d,ll r){
	h[v]*=w;
	h[v]%=k;
	if(d==r)return;
	for(auto i : g[v]){
		if(i==p)continue;
		dfs(i,v,w,d+1,r);
	}
}
void dfs2(ll v){
	for(auto i : g[v]){
		if(i==p[v])continue;
		p[i]=v;
		dfs2(i);
	}
}
void solve(){
	ll i,j,q;
	ll a,b,c;
	cin>>n>>k;
	for(i=0;i<=n;i++){
		for(j=0;j<=45;j++)val[i][j]=1;
	}
	for(i=1;i<n;i++){
		cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}
	for(i=1;i<=n;i++)cin>>h[i];
	dfs2(1);
	cin>>q;
	ll t;
	for(i=0;i<q;i++){
		cin>>t;
		if(t==1){
			cin>>a>>b>>c;
			while(b>0){
				val[a][b]*=c;
				val[a][b-1]*=c;
				val[a][b]%=k;
				val[a][b-1]%=k;
				b--;
				if(p[a]==0)break;
				a=p[a];
			}
			while(b){
				val[a][b]*=c;
				val[a][b]%=k;
				b--;
			}
			val[a][0]*=c;
			val[a][0]%=k;
		}else{
			cin>>a;
			b=a;
			ll ans=h[a]*val[a][0]%k;
			for(j=1;j<=40;j++){
				a=p[a];
				if(a==0)break;
				ans*=val[a][j];
				ans%=k;
			}
			cout<<ans<<endl;
		}
	}
}
signed main(){
	start();
    ll t=1;
	//cin>>t;
    while(t--) solve();
    return 0;
}
/*
1
7
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7






*/

Compilation message

sprinkler.cpp: In function 'void fre(std::string)':
sprinkler.cpp:43:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:43:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 373 ms 105716 KB Output is correct
3 Correct 246 ms 106068 KB Output is correct
4 Correct 364 ms 110896 KB Output is correct
5 Correct 316 ms 105808 KB Output is correct
6 Correct 256 ms 105728 KB Output is correct
7 Correct 253 ms 106212 KB Output is correct
8 Correct 201 ms 106688 KB Output is correct
9 Correct 457 ms 113488 KB Output is correct
10 Correct 285 ms 113360 KB Output is correct
11 Incorrect 352 ms 105528 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 373 ms 105716 KB Output is correct
3 Correct 246 ms 106068 KB Output is correct
4 Correct 364 ms 110896 KB Output is correct
5 Correct 316 ms 105808 KB Output is correct
6 Correct 256 ms 105728 KB Output is correct
7 Correct 253 ms 106212 KB Output is correct
8 Correct 201 ms 106688 KB Output is correct
9 Correct 457 ms 113488 KB Output is correct
10 Correct 285 ms 113360 KB Output is correct
11 Incorrect 352 ms 105528 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7256 KB Output is correct
2 Correct 474 ms 110420 KB Output is correct
3 Correct 568 ms 109136 KB Output is correct
4 Correct 452 ms 108880 KB Output is correct
5 Correct 336 ms 102736 KB Output is correct
6 Correct 267 ms 102964 KB Output is correct
7 Correct 250 ms 103068 KB Output is correct
8 Correct 202 ms 103368 KB Output is correct
9 Correct 461 ms 107996 KB Output is correct
10 Correct 568 ms 110164 KB Output is correct
11 Correct 375 ms 102376 KB Output is correct
12 Correct 393 ms 103500 KB Output is correct
13 Correct 311 ms 104140 KB Output is correct
14 Correct 331 ms 105076 KB Output is correct
15 Correct 2 ms 7000 KB Output is correct
16 Correct 2 ms 7004 KB Output is correct
17 Correct 2 ms 7004 KB Output is correct
18 Correct 2 ms 7000 KB Output is correct
19 Correct 2 ms 7004 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Incorrect 505 ms 110224 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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