oj.uz

Submission #615397

# Submission time Handle Problem Language Result Execution time Memory
615397 2022-07-31T08:55:54 Z 장태환(#8493) Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 86968 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int N, L;
int pw[1000100];
struct st
{
	vector<int>r;
	int treeN;
	void init(int cnt)
	{
		for (treeN = 1; treeN < cnt; treeN *= 2);
		r.resize(2 * treeN + 3, 0);
	}
	void upd(int qs, int qe,int n, int s, int e, int i = 1)
	{
		if (s > qe || qs > e)
			return;
		if (qs <= s && e <= qe)
		{
			r[i]++;
			return;
		}
		upd(qs, qe, n, s, (s + e) / 2, i * 2);
		upd(qs, qe, n, (s + e) / 2 + 1, e, i * 2 + 1);
	}
	int ge(int qs, int qe, int n,int i = 1)
	{
		if (qs == qe)
		{
			return r[i];
		}
		int m = (qs + qe) / 2;
		if (n > m)
		{
			return r[i]+ge(m+1,qe, n, i * 2 + 1);
		}
		else
		{
			return r[i]+ge(qs, m, n, i * 2);
		}
	}
}arr[200100];
int d[201000];
int pos[200100];
int par[200100];
int st[201000];
int en[200100];
int c;
vector<int>li[201000];
vector<pair<int,int>>dl[200100];
vector<int>dl2[200100];
void dfs(int n,int p=0)
{
	st[n] = ++c;
	dl[d[n]].push_back({ st[n],n });
	dl2[d[n]].push_back(st[n]);
	int i;
	for (i = 0; i < li[n].size(); i++)
	{
		if (li[n][i] == p)
			continue;
		par[li[n][i]] = n;
		d[li[n][i]] = d[n] + 1;
		dfs(li[n][i],n);
	}
	en[n] = c;
}
int pp[200100];
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> L;
	int i;
	for (i = 1; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		li[a].push_back(b);
		li[b].push_back(a);
	}
	pw[0] = 1;
	for (i = 1; i <= 1000000; i++)
	{
		pw[i] = pw[i - 1] * 2 % L;
	}
	dfs(1);
	for (i = 0; i <= N; i++)
	{
		arr[i].init(dl[i].size());
		int j;
		for (j = 0; j < dl[i].size(); j++)
		{
			pos[dl[i][j].second] = j;
		}
	}
	for (i = 1; i <= N; i++)
	{
		int a;
		cin >> a;
		pp[i] = a;
	}
	int Q;
	cin >> Q;
	while (Q--)
	{
		int a;
		cin >> a;
		if (a == 1)
		{
			int b, c, w;
			cin >> b >> c >> w;
			int j;
			int dp = d[b];
			int cp = b;
			for (j = dp + c; j >= dp - c; j--)
			{
				if (j + dp - d[cp] * 2 + 2 <= c && cp != 1)
				{
					cp = par[cp];
				}
				if (j < 0)
					break;
				int lp = lower_bound(dl2[j].begin(), dl2[j].end(), st[cp]) - dl2[j].begin();
				int rp = lower_bound(dl2[j].begin(), dl2[j].end(), en[cp]+1) - dl2[j].begin()-1;
				if (lp <= rp)
				{
					arr[j].upd(lp, rp, w, 0, arr[j].treeN - 1);
				}
				
			}
		}
		else
		{
			int b;
			cin >> b;
			cout << pp[b]*pw[arr[d[b]].ge(0, arr[d[b]].treeN - 1, pos[b])]%L << '\n';
		}
	}

}

Compilation message

sprinkler.cpp: In function 'void dfs(long long int, long long int)':
sprinkler.cpp:59:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (i = 0; i < li[n].size(); i++)
      |              ~~^~~~~~~~~~~~~~
sprinkler.cpp: In function 'int main()':
sprinkler.cpp:93:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |   for (j = 0; j < dl[i].size(); j++)
      |               ~~^~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28500 KB Output is correct
2 Incorrect 18 ms 28500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 28532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 28532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 28540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28492 KB Output is correct
2 Correct 712 ms 82036 KB Output is correct
3 Correct 2713 ms 76572 KB Output is correct
4 Correct 1097 ms 77336 KB Output is correct
5 Correct 2343 ms 68552 KB Output is correct
6 Correct 1554 ms 67608 KB Output is correct
7 Correct 1152 ms 66520 KB Output is correct
8 Correct 343 ms 66180 KB Output is correct
9 Correct 676 ms 86968 KB Output is correct
10 Correct 2225 ms 83560 KB Output is correct
11 Correct 1165 ms 69740 KB Output is correct
12 Execution timed out 4008 ms 66700 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28500 KB Output is correct
2 Incorrect 18 ms 28500 KB Output isn't correct
3 Halted 0 ms 0 KB -