Submission #568077

#	Time	Username	Problem	Language	Result	Execution time	Memory
568077		lovemathboy	Sprinkler (JOI22_sprinkler)	C++14	100 / 100	1755 ms	103160 KiB

sprinkler

#include <bits/stdc++.h>
using namespace std;

int n, mod, q;
vector<vector<long long> > a;
vector<vector<int> > adj;
vector<int> p;

void root(int x, int par) {
	p[x] = par;
	for (int i = 0; i < adj[x].size(); i++) {
		int v = adj[x][i];
		if (v != par) root(v, x);
	}
}

int main() {
	scanf("%d %d", &n, &mod);
	a.resize(n+1); adj.resize(n+1); p.resize(n+1, -1);
	for (int i = 0; i <= n; i++) {
		a[i].resize(41, 1);
	}
	int i1, i2, i3;
	for (int i = 0; i < n-1; i++) {
		scanf("%d %d", &i1, &i2);
		adj[i1].push_back(i2);
		adj[i2].push_back(i1);
	}
	root(1, -1);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i][0]);
	scanf("%d", &q);
	int v, w, d;
	while (q--) {
		scanf("%d", &i1);
		if (i1 == 1) {
			scanf("%d %d %d", &v, &d, &w);
			while (p[v] != -1 && d > 0) {
				a[v][d] = (a[v][d] * w) % mod;
				a[v][d - 1] = (a[v][d - 1] * w) % mod;
				d--; v = p[v];
			}
			for (int i = 0; i <= d; i++) a[v][i] = (a[v][i] * w) % mod;
		} else {
			scanf("%d", &v);
			long long sum = a[v][0] % mod;
			v = p[v]; 
			int cnt = 1;
			while (v != -1 && cnt <= 40) {
				sum = (sum * a[v][cnt]) % mod;
				v = p[v]; cnt++;
			}
			printf("%lld\n", sum);
		}
	}
	return 0;
}

Compilation message (stderr)

sprinkler.cpp: In function 'void root(int, int)':
sprinkler.cpp:11:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for (int i = 0; i < adj[x].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:23:14: warning: unused variable 'i3' [-Wunused-variable]
   23 |  int i1, i2, i3;
      |              ^~
sprinkler.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d %d", &n, &mod);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
sprinkler.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%d %d", &i1, &i2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
sprinkler.cpp:30:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |  for (int i = 1; i <= n; i++) scanf("%lld", &a[i][0]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~
sprinkler.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
sprinkler.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d", &i1);
      |   ~~~~~^~~~~~~~~~~
sprinkler.cpp:36:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |    scanf("%d %d %d", &v, &d, &w);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sprinkler.cpp:44:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |    scanf("%d", &v);
      |    ~~~~~^~~~~~~~~~

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