Submission #629024

#	Time	Username	Problem	Language	Result	Execution time	Memory
629024		iomoon191	Sprinkler (JOI22_sprinkler)	C++17	3 / 100	53 ms	84580 KiB

sprinkler

#include<bits/stdc++.h>
#define int long long
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
#define pb push_back
#define fi first
#define se second
#define For(i,a,b) for(int i=(a); i<=(b); ++i)
#define roF(i,a,b) for(int i=(a); i>=(b); --i)
using namespace std;
#ifdef DEBUG__
void dmpr(ostream &os){ os << "\n"; }
template<class T, class... Args>
void dmpr(ostream &os, const T &t, const Args &... args){
	os << t << " ";
	dmpr(os, args...);
}
#define dbg(...) dmpr(cerr, __LINE__, ##__VA_ARGS__)
#else
#define dbg(...) void(0)
#endif
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef long long ll;
typedef long double ld;
const int N=100005;
const int inf=0x3f3f3f3f;
mt19937 rng(random_device {}()); 
int rand(int a){
	return rng()%a;
}
int mod;
struct mint {
    int val;
    mint(){ val = 0; }
    mint(const ll& v) {
        val=(-mod <= v and v < mod) ? v : v%mod;
        if (val < 0) val+=mod;
    }
    friend bool operator==(const mint& a, const mint& b){ return a.val == b.val; }
    friend bool operator!=(const mint& a, const mint& b){ return !(a == b); }
    friend ostream& operator<<(ostream& os, const mint& a){ return os << a.val; }
    friend bool operator<(const mint& a, const mint& b){ return a.val < b.val; }
    mint operator-()const{ return mint(-val); }
    mint& operator+=(const mint& m){ 
    	if((val+=m.val) >= mod) val-=mod; 
    	return *this; 
    }
    mint& operator-=(const mint& m){ 
    	if ((val-=m.val) < 0) val+=mod; 
    	return *this; 
    }
    mint& operator*=(const mint& m){ 
    	val=(ll)val*m.val%mod; 
    	return *this; 
    }
    friend mint ipow(mint a, ll p) {
        mint ans=1; 
        for(; p; p >>= 1, a*=a) if (p&1) ans*=a;
        return ans;
    }
    friend mint inv(const mint& a){ 
    	assert(a.val); 
    	return ipow(a, mod-2); 
    }
    mint& operator /= (const mint& m){ 
    	return (*this) *= inv(m); 
    }
    friend mint operator+(mint a, const mint& b){ return a+=b; }
    friend mint operator-(mint a, const mint& b){ return a-=b; }
    friend mint operator*(mint a, const mint& b){ return a*=b; }
    friend mint operator/(mint a, const mint& b){ return a/=b; }
    operator int64_t() const{ return val; }
};
vi adj[N];
int n, l, par[N], dep[N], zin[N], zout[N], piv;
mint dp[N][50];
void dfs(int x, int p){
	zin[x]=++piv;
	for(auto &i: adj[x]){
		if(i == p) continue;
		dep[i]=dep[x]+1;
		par[i]=x;
		dfs(i, x);
	}
	zout[x]=piv;
}
void rmain(){
	cin >> n >> l;
	mod=l;
	For(i,2,n){
		int u, v; cin >> u>> v;
		adj[v].pb(u);
		adj[u].pb(v);
	}
	For(i,n+1,n+50){
		adj[i].pb(i+1);
		adj[i+1].pb(i);
	}
	adj[1].pb(n+1);
	adj[n+1].pb(1);
	n+=50;
	dfs(n, -1);
	For(i,1,n) For(j,0,45) dp[i][j]=mint(1);
	For(i,1,n-50){
		int x; cin >> x;
		dp[i][0]*=mint(x);
	}
	int q; cin >> q;
	while(q--){
		int t; cin >> t;
		if(t == 1){
			int v, d, w;
			cin >> v >> d >> w;
			vi sk;
			For(i,0,d){
				sk.pb(v);
				v=par[v];
			}
			For(i,0,d){
				if(i < d) dp[sk[i]][d-i-1]*=mint(w);
				dp[sk[i]][d-i]*=mint(w);
			}
		}
		else{
			int v; cin >> v;
			mint res=1;
			For(i,0,45){
				res*=dp[v][i];
				v=par[v];
			}
			cout << res << "\n";
		}
	}
}

signed main(int argc, char *argv[]){
	iostream::sync_with_stdio(0);
	int T=1; 
	while(T--) rmain();
	return 0;
}

Compilation message (stderr)

sprinkler.cpp:137:8: warning: first argument of 'int main(long long int, char**)' should be 'int' [-Wmain]
  137 | signed main(int argc, char *argv[]){
      |        ^~~~

• Subtask 1: 3 / 3
• Subtask 2: 0 / 9
• Subtask 3: 0 / 29
• Subtask 4: 0 / 12
• Subtask 5: 0 / 30
• Subtask 6: 0 / 17