oj.uz

Submission #571010

# Submission time Handle Problem Language Result Execution time Memory
571010 2022-06-01T02:50:27 Z jjang36524 Inside information (BOI21_servers) C++14
0 / 100
 154 ms 24268 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#pragma warning(disable:4996)
#define int long long
using namespace std;
int siz[200100];
int done[200100];
int ans[120100];
vector<pair<int, int>>chkq[120100];
vector<int>q[120100];
vector<pair<int, int>>t[200100];
int N, K;
bool cmp(pair<int, int>a, pair<int, int>b)
{
	if (a.second != b.second)
		return a.second < b.second;
	return a < b;
}
int sz(int n, int par)
{
	int i;
	siz[n] = 1;
	for (i = 0; i < t[n].size(); i++)
	{
		if (done[t[n][i].first] || t[n][i].first == par)
			continue;
		siz[n] += sz(t[n][i].first, n);
	}
	return siz[n];
}
int rt[200100];
int fw[500100];
void u(int n, int k)
{
	while (n <= N +K)
	{
		fw[n] += k;
		n += n & -n;
	}
}
int res(int n)
{
	int ans = 0;
	while (n)
	{
		ans += fw[n];
		n -= n & -n;
	}
	return ans;
}
void intcal(int n, int p, int lv)
{
	rt[n] = lv;
	u(lv, 1);
	int i;
	for (i = 0; i < t[n].size(); i++)
	{
		if (t[n][i].first != p && !done[t[n][i].first] && t[n][i].second >= lv)
		{
			intcal(t[n][i].first, n, t[n][i].second);
		}
	}
}
void leave(int n, int p, int lv)
{
	rt[n] = 998244353;
	u(lv, -1);
	int i;
	for (i = 0; i < t[n].size(); i++)
	{
		if (t[n][i].first != p && !done[t[n][i].first] && t[n][i].second >= lv)
		{
			leave(t[n][i].first, n, t[n][i].second);
		}
	}
}
void givans(int n)
{
	int i;
	for (i = 0; i < chkq[n].size(); i++)
	{
		if (rt[chkq[n][i].first] <= chkq[n][i].second)
			ans[chkq[n][i].second] = -1;
	}
	for (i = 0; i < q[n].size(); i++)
	{
		ans[q[n][i]] += res(q[n][i]);
	}
}
void soldfs(int n, int p, int lv)
{
	givans(n);
	int i;
	for (i = 0; i < t[n].size(); i++)
	{
		if (t[n][i].first != p && !done[t[n][i].first] && t[n][i].second <= lv)
		{
			soldfs(t[n][i].first, n, t[n][i].second);
		}
	}
}
int getsen(int n, int par, int lim)
{
	int i;
	for (i = 0; i < t[n].size(); i++)
	{
		if (done[t[n][i].first] || t[n][i].first == par)
			continue;
		if (lim < siz[t[n][i].first])
			return getsen(t[n][i].first, n, lim);
	}
	return n;
}

void cendec(int n,int p)
{
	sz(n, -1);
	int r = getsen(n, -1, siz[n] / 2);
	int i;
	sort(t[r].begin(), t[r].end(),cmp);
	intcal(r, 0, 1);
	givans(r);
	
	for (i = 0; i < t[r].size(); i++)
	{
		if (t[r][i].first != p && !done[t[r][i].first])
		{
			leave(t[r][i].first, r, t[r][i].second);
			u(rt[r], -1);
			rt[r] = t[r][i].second;
			u(rt[r], 1);
			soldfs(t[r][i].first, r, t[r][i].second);
		}
	}
	done[r] = 1;
	u(rt[r], -1);
	rt[r] = 998244353;
	for (i = 0; i < t[r].size(); i++)
	{
		if (t[r][i].first != p && !done[t[r][i].first])
		{
			cendec(t[r][i].first, r);
		}
	}
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> K;
	int i;
	for (i = 1; i < N+K; i++)
	{
		char a;
		cin >> a;
		if (a == 'S')
		{
			int b, c;
			cin >> b >> c;
			t[b].push_back({ c,i+1});
			t[c].push_back({ b,i+1 });
			ans[i+1] = -3;
		}
		else if (a == 'Q')
		{
			int b, c;
			cin >> b >> c;
			chkq[c].push_back({ b,i+1 });
			ans[i+1] = -2;
		}
		else
		{
			int b;
			cin >> b;
			q[b].push_back(i+1);
		}
	}
	memset(rt, 1, sizeof(rt));
	cendec(1,0);
	for (i = 2; i <= N + K; i++)
	{
		if (ans[i] >= -2)
		{
			if (ans[i] == -2)
				cout << "no" << '\n';
			else if (ans[i] == -1)
				cout << "yes" << '\n';
			else
				cout << ans[i] << '\n';
		}
	}
}

Compilation message

servers.cpp:5: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    5 | #pragma warning(disable:4996)
      | 
servers.cpp: In function 'long long int sz(long long int, long long int)':
servers.cpp:25:16: 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]
   25 |  for (i = 0; i < t[n].size(); i++)
      |              ~~^~~~~~~~~~~~~
servers.cpp: In function 'void intcal(long long int, long long int, long long int)':
servers.cpp:58:16: 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]
   58 |  for (i = 0; i < t[n].size(); i++)
      |              ~~^~~~~~~~~~~~~
servers.cpp: In function 'void leave(long long int, long long int, long long int)':
servers.cpp:71:16: 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]
   71 |  for (i = 0; i < t[n].size(); i++)
      |              ~~^~~~~~~~~~~~~
servers.cpp: In function 'void givans(long long int)':
servers.cpp:82:16: 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]
   82 |  for (i = 0; i < chkq[n].size(); i++)
      |              ~~^~~~~~~~~~~~~~~~
servers.cpp:87: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]
   87 |  for (i = 0; i < q[n].size(); i++)
      |              ~~^~~~~~~~~~~~~
servers.cpp: In function 'void soldfs(long long int, long long int, long long int)':
servers.cpp:96:16: 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]
   96 |  for (i = 0; i < t[n].size(); i++)
      |              ~~^~~~~~~~~~~~~
servers.cpp: In function 'long long int getsen(long long int, long long int, long long int)':
servers.cpp:107:16: 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]
  107 |  for (i = 0; i < t[n].size(); i++)
      |              ~~^~~~~~~~~~~~~
servers.cpp: In function 'void cendec(long long int, long long int)':
servers.cpp:126:16: 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]
  126 |  for (i = 0; i < t[r].size(); i++)
      |              ~~^~~~~~~~~~~~~
servers.cpp:140:16: 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]
  140 |  for (i = 0; i < t[r].size(); i++)
      |              ~~^~~~~~~~~~~~~

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 17108 KB Output is correct
2 Incorrect 36 ms 16904 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 17108 KB Output is correct
2 Incorrect 36 ms 16904 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17132 KB Output is correct
2 Incorrect 123 ms 23868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17132 KB Output is correct
2 Incorrect 123 ms 23868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17024 KB Output is correct
2 Incorrect 139 ms 24100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 17024 KB Output is correct
2 Incorrect 139 ms 24100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17060 KB Output is correct
2 Incorrect 114 ms 24268 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17060 KB Output is correct
2 Incorrect 114 ms 24268 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17176 KB Output is correct
2 Incorrect 154 ms 24040 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 17176 KB Output is correct
2 Incorrect 154 ms 24040 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17064 KB Output is correct
2 Incorrect 39 ms 16900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17064 KB Output is correct
2 Incorrect 39 ms 16900 KB Output isn't correct
3 Halted 0 ms 0 KB -