oj.uz

Submission #615440

# Submission time Handle Problem Language Result Execution time Memory
615440 2022-07-31T09:12:56 Z 장태환(#8493) Sprinkler (JOI22_sprinkler) C++17
0 / 100
 4000 ms 75880 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
int N, L;
int qs, qe,n;
struct st
{
	vector<long long>r;
	int treeN;
	void init(int cnt)
	{
		for (treeN = 1; treeN < cnt; treeN *= 2);
		r.resize(2 * treeN + 3, 0);
	}
	void upd( int s, int e, int i = 1)
	{
		if (s > qe || qs > e)
			return;
		if (qs <= s && e <= qe)
		{
			r[i]++;
			return;
		}
		upd(s, (s + e) / 2, i * 2);
		upd((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];
long long pw[400100];
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 aaa[200100];
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.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 <= 400010; 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;
		aaa[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();
				if (lp!=dl2[j].size()&&dl2[j][lp]<=en[cp])
				{
					int rp = lower_bound(dl2[j].begin(), dl2[j].end(), en[cp] + 1) - dl2[j].begin() - 1;
					qs = lp;
					qe = rp;
					n = w;
					arr[j].upd(0, arr[j].treeN - 1);
				}

			}
		}
		else
		{
			int b;
			cin >> b;
			cout << pw[arr[d[b]].ge(0, arr[d[b]].treeN - 1, pos[b])]*aaa[b]%L << '\n';
		}
	}

}

Compilation message

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

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 15 ms 23840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 594 ms 69332 KB Output is correct
3 Correct 2025 ms 64232 KB Output is correct
4 Correct 955 ms 66592 KB Output is correct
5 Correct 2189 ms 57040 KB Output is correct
6 Correct 1528 ms 56524 KB Output is correct
7 Correct 1139 ms 55664 KB Output is correct
8 Correct 365 ms 55760 KB Output is correct
9 Correct 623 ms 75880 KB Output is correct
10 Correct 2051 ms 73048 KB Output is correct
11 Correct 1199 ms 58144 KB Output is correct
12 Execution timed out 4027 ms 55080 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 15 ms 23840 KB Output isn't correct
3 Halted 0 ms 0 KB -