답안 #589031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589031	2022-07-04T08:55:39 Z	LastRonin	Sprinkler (JOI22_sprinkler)	C++14	컴파일 오류	0 ms	0 KB

sprinkler

#pragma GCC optimize("O3")
 
#include <bits/stdc++.h> 
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
 
const int N = 2e5 + 11;
const ll hsh[2] = {1555555699, 1222222763};
const ll P = 113;
 
mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());
 
ll n, L, q;
vector<ll> g[N];
ll sz[N];
ll h[N];
int lay[N];
ll dist[N][20];
ll cp[N];// centroid predok
bool del[N];
 
void dfs(ll v, ll p) {
	sz[v] = 1;
	for(auto u : g[v]) {
		if(p == u || del[u])continue;
		dfs(u, v);
		sz[v] += sz[u];
	}
}
 
void bdfs(ll v, ll p, ll k) {
	cp[v] = k;
	if(p == k)dist[v][lay[k]] = 1;
	else dist[v][lay[k]] = dist[p][lay[k]] + 1;
	for(auto u : g[v]) {
		if(u == p || del[u])continue;
		bdfs(u, v, k);
	}
}
 
int fnd(int v) {
	int p = 0;
	int siz = sz[v];
	while(p != v) {
		int c = v;
		for(auto u : g[c]) {
			if(u != p && !del[u] && sz[u] * 2ll > siz) {
				v = u;
				break;
			}
		}
		p = c;
	}
	return v;
}
 
void build(ll v, ll layer = 0) {
	dfs(v, 0);
	v = fnd(v);
	del[v] = 1;
	lay[v] = layer;
	for(auto u : g[v]) {
		if(!del[u])
			bdfs(u, v, v);	          	
	}
	for(auto u : g[v]) {
		if(!del[u]) {
			build(u, layer + 1);
		}
	}
}
 
ll stp[N][42];
ll per[N][42];
 
 
void upd(ll a, ll c, ll b) {
	ll dis = 0;
	ll izn = a;
	int cnt = 0;
	const ll modu = L;
	ll kk = b;
	for(int j = c; j >= 0; j--) {
		stp[a][j] = stp[a][j] * kk % modu;
		//kk = kk * b % modu;
	}
	while(a) {
		if(cp[a] == 0)break;
		cnt++;
		dis = dist[izn][lay[cp[a]]];
		if(c - dis >= 0) {
			kk = b;
			for(int j = c - dis; j >= 0; j--) {
				stp[cp[a]][j] = stp[cp[a]][j] * kk % modu;
				per[a][j] = per[a][j] * kk % modu;
				//kk = kk * b % modu; 
			}
			//add1(cp[a], c - dis, b);
			//add2(a, c - dis, b);
		}				
		a = cp[a];
	}
}
 
ll phi = 0;
 
ll bp(ll a, ll b) {
	const ll z = L;
	ll c = 1ll;
	while(b) {
		if(b&1)
			c = c * a % z;
		b >>= 1ll;
		a = a * a % z;		
	}
	return c;
}
 
ll inv(ll a) {
	return bp(a, phi - 1);
}
 
ll getans(ll a) {
	ll dis = 0;
	ll izn = a;
	ll ans = stp[a][0];
	ll pr = a;
	const ll modu = L;
	a = cp[a];
	while(a) {
		dis = dist[izn][lay[a]];
		ll z = stp[a][min(41, dis)] * inv(per[pr][min(41, dis)]) % modu;
		ans = ans * z % modu;
		pr = a;
		a = cp[a];				
	}
	return ans;
}
 
ll prec[N * 3];
 
int main() {
	speed;
	cin >> n >> L;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j <= 41; j++)
			stp[i][j] = per[i][j] = 1;
	}
	prec[0] = 1;
	ll ts = L;
	ll ans = L;
	for(int i = 2; i * i <= L; i++) {
		if(L % i == 0) {
			while(L % i == 0)L /= i;
			ans = ans - ans/i;
		}
	}
	if(L > 1)ans = ans - ans/L;
	phi = ans;
	L = ts;
	for(int i = 1; i <= 500000; i++)
		prec[i] = prec[i - 1] * 2ll % L;	
	for(int i = 1, a, b; i < n; i++) {
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);		
	}
	for(int i = 1; i <= n; i++) {
		cin >> h[i];	
	}
	build(1);
	cin >> q;
	while(q--) {
		ll t, a, b, c;
		cin >> t >> a;
		if(t == 1) {
			cin >> b >> c;
			upd(a, b, c);
		} else {
			cout << h[a] * getans(a) % L << '\n';
		}
	}
	
}
/*
6 10
5 6
1 2
1 4
2 6
3 6
9
2
3
4
9
1
6
1 5 1 7
1 4 1 9
1 5 0 7
1 1 1 3
1 6 1 4
2 4
*/

Compilation message

sprinkler.cpp: In function 'long long int getans(long long int)':
sprinkler.cpp:138:28: error: no matching function for call to 'min(int, long long int&)'
  138 |   ll z = stp[a][min(41, dis)] * inv(per[pr][min(41, dis)]) % modu;
      |                            ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sprinkler.cpp:3:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:138:28: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  138 |   ll z = stp[a][min(41, dis)] * inv(per[pr][min(41, dis)]) % modu;
      |                            ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sprinkler.cpp:3:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:138:28: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  138 |   ll z = stp[a][min(41, dis)] * inv(per[pr][min(41, dis)]) % modu;
      |                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sprinkler.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:138:28: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  138 |   ll z = stp[a][min(41, dis)] * inv(per[pr][min(41, dis)]) % modu;
      |                            ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sprinkler.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:138:28: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  138 |   ll z = stp[a][min(41, dis)] * inv(per[pr][min(41, dis)]) % modu;
      |                            ^
sprinkler.cpp:138:56: error: no matching function for call to 'min(int, long long int&)'
  138 |   ll z = stp[a][min(41, dis)] * inv(per[pr][min(41, dis)]) % modu;
      |                                                        ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sprinkler.cpp:3:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:138:56: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  138 |   ll z = stp[a][min(41, dis)] * inv(per[pr][min(41, dis)]) % modu;
      |                                                        ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sprinkler.cpp:3:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:138:56: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  138 |   ll z = stp[a][min(41, dis)] * inv(per[pr][min(41, dis)]) % modu;
      |                                                        ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sprinkler.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:138:56: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  138 |   ll z = stp[a][min(41, dis)] * inv(per[pr][min(41, dis)]) % modu;
      |                                                        ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sprinkler.cpp:3:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
sprinkler.cpp:138:56: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  138 |   ll z = stp[a][min(41, dis)] * inv(per[pr][min(41, dis)]) % modu;
      |                                                        ^