Submission #617436

#	Time	Username	Problem	Language	Result	Execution time	Memory
617436		patrikpavic2	Sprinkler (JOI22_sprinkler)	C++17	41 / 100	4113 ms	686264 KiB

sprinkler

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef vector < int > vi;
typedef long long ll;

const int N = 2e5 + 500;
const int LOG = 20;
const int INF = 0x3f3f3f3f;

int MOD;

inline int mul(int A, int B){
	return (ll)A * B % MOD;
}

struct tournament{
	int siz, off;
	vi T;
	void init(int _siz){
		siz = _siz; off = 1;
		while(off < siz) off <<= 1;
		T.resize(2 * off);
		for(int &x : T) x = 1;
	}
	int get(int x){
		int ret = 1;
		for(x = (x + off); x ; x /= 2)
			ret = mul(ret, T[x]);
		return ret;
	}
	void Tmultiply(int i, int a, int b, int lo, int hi, int x){
		if(lo <= a && b <= hi) { T[i] = mul(T[i], x); return; }
		if(a > hi || b < lo) return;
		Tmultiply(2 * i, a, (a + b) / 2, lo, hi, x);
		Tmultiply(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x);
	}
	inline void multiply(int l, int r, int x){
		if(r < l ) return;
		Tmultiply(1, 0, off - 1, l, r, x);
	}
};

tournament T[N][41];
int cen[N], siz[N], par[N], dep[N][LOG], gore[N], tko[N][41];
vector < int > pos;
int L[N][41], R[N][41], gdje[N][LOG], osb[N], gdje2[N][LOG];
int n, q;
vector < int > v[N];

void dfs(int x, int lst){
	siz[x] = 1; pos.PB(x);
	for(int y : v[x]){
		if(cen[y] != INF || y == lst) continue;
		dfs(y, x); siz[x] += siz[y];
	}
}

int TATA, RAZ;

void dfs2(int x, int lst, int dis){
	gdje2[x][RAZ] = dis;
	if(dis <= 40) {
		gdje[x][RAZ] = tko[TATA][dis];
		tko[TATA][dis]++;
	}
	for(int y : v[x]){
		if(y == lst || cen[y] <= RAZ) continue;
		dfs2(y, x, dis + 1);
	}
}

int nadi_centroid(int x){
	pos.clear(); dfs(x, x); 
	int bst = x;
	for(int y : pos)
		if(2 * siz[y] >= (int)pos.size() && siz[y] < siz[bst])
			bst = y;
	return bst;
}


int centroidna(int x, int dub){
	x = nadi_centroid(x);
	cen[x] = dub;
	for(int y : v[x]){
		if(cen[y] != INF) continue;
		int nov = centroidna(y, dub + 1);
		for(int i = 1;i <= 40;i++)
			L[nov][i] = tko[x][i];
		TATA = x; RAZ = dub;
		dfs2(y, x, 1);
		for(int i = 1;i <= 40;i++)
			R[nov][i] = tko[x][i] - 1;
		par[nov] = x; 
	}
	return x;
}

void obradi(int x, int d, int k){
	osb[x] = mul(osb[x], k);
	for(int i = 1;i <= d;i++) 
		T[x][i].multiply(0, T[x][i].siz - 1, k);
	int lst = x, poc = x; 
	x = par[x]; 
	while(x){
		if(gdje2[poc][cen[x]] <= d)
			osb[x] = mul(osb[x], k);		
		for(int i = 1;i <= d - gdje2[poc][cen[x]];i++){
			T[x][i].multiply(0, L[lst][i] - 1, k);
			T[x][i].multiply(R[lst][i] + 1, T[x][i].siz - 1, k);
		}
		lst = x; x = par[x];	
	}
}

int get(int x){
	int ret = osb[x];
	int cur = x;
	while(cur){
		if(gdje[x][cen[cur]] != -1){
			ret = mul(ret, T[cur][gdje2[x][cen[cur]]].get(gdje[x][cen[cur]]));
		}
		cur = par[cur];
	}
	return ret;
	
}

int main(){
	memset(cen, INF, sizeof(cen));
	memset(gdje, -1, sizeof(gdje));
	scanf("%d%d", &n, &MOD);
	for(int i = 1;i < n;i++){
		int x, y; scanf("%d%d", &x, &y);
		v[x].PB(y), v[y].PB(x);
	}
	for(int i = 1;i <= n;i++)
		scanf("%d", osb + i);
	centroidna(1, 1);
	for(int i = 1;i <= n;i++)
		for(int j = 0;j <= 40;j++)
			T[i][j].init(tko[i][j]);
	scanf("%d", &q);
	for(;q--;){
		int ty; scanf("%d", &ty);
		if(ty == 2){
			int x; scanf("%d", &x);
			printf("%d\n", get(x));
		}
		else{
			int x, d, k; scanf("%d%d%d", &x, &d, &k);
			obradi(x, d, k);
		}
	}
	return 0;
}

Compilation message (stderr)

sprinkler.cpp: In function 'int main()':
sprinkler.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |  scanf("%d%d", &n, &MOD);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
sprinkler.cpp:143:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~
sprinkler.cpp:147:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |   scanf("%d", osb + i);
      |   ~~~~~^~~~~~~~~~~~~~~
sprinkler.cpp:152:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
sprinkler.cpp:154:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |   int ty; scanf("%d", &ty);
      |           ~~~~~^~~~~~~~~~~
sprinkler.cpp:156:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~
sprinkler.cpp:160:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |    int x, d, k; scanf("%d%d%d", &x, &d, &k);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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