제출 #416981

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
416981		aryan12	Inside information (BOI21_servers)	C++17	52.50 / 100	419 ms	83764 KiB

servers

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

const int N = 120005;
vector<pair<int, int> > g[N];
int cnt = 0;
int DP[20][N], isDecreasing[20][N], isIncreasing[20][N];
int depth[N];

void dfs(int node, int par) {
	//cout << "node = " << node << "\n";
	DP[0][node] = par;
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i].first != par) {
			isDecreasing[0][g[node][i].first] = g[node][i].second;
			isIncreasing[0][g[node][i].first] = g[node][i].second;
			depth[g[node][i].first] = depth[node] + 1;
			dfs(g[node][i].first, node);
		}
	}
}

int LCA(int x, int y) {
	if(depth[x] < depth[y]) {
		swap(x, y);
	}
	int diff = depth[x] - depth[y];
	for(int i = 19; i >= 0; i--) {
		if(diff >= (1 << i)) {
			diff -= (1 << i);
			x = DP[i][x];
		}
	}
	if(x == y)
		return x;
	for(int i = 19; i >= 0; i--) {
		if(DP[i][x] != DP[i][y]) {
			x = DP[i][x];
			y = DP[i][y];
		}
	}
	return DP[0][x];
}

bool Satisfied(int a, int b, int cnt) {
	int lca = LCA(a, b);
	int diff = depth[b] - depth[lca];
	int maxval = -1;
	int lastvalhere = -1;
	int prevval = -1;
	for(int i = 19; i >= 0; i--) {
		if(diff >= (1 << i)) {
			diff -= (1 << i);
			if(isIncreasing[i][b] == -1 || isIncreasing[0][b] <= prevval) {
				return false;
			}
			maxval = max(maxval, isIncreasing[i][b]);
			lastvalhere = max(lastvalhere, isIncreasing[i][b]);
			prevval = isIncreasing[i][b];
			b = DP[i][b];
		}
	}
	diff = depth[a] - depth[b];
	if(diff != 0) {
		maxval = max(maxval, isDecreasing[0][a]);
	}
	//cout << "lastvalhere = " << lastvalhere << "\n";
	prevval = INT_MAX;
	for(int i = 19; i >= 0; i--) {
		if(diff >= (1 << i)) {
			diff -= (1 << i);
			if(isDecreasing[i][a] == -1 || isDecreasing[0][a] >= prevval) {
				return false;
			}
			if(diff == 0) {
				if(lastvalhere >= isDecreasing[i][a]) {
					return false;
				}
			}
			prevval = isDecreasing[i][a];
			a = DP[i][a];
		}
	}
	//cout << "cnt = " << cnt << ", maxval = " << maxval << "\n";
	if(maxval > cnt)
		return false;
	return true;
}

int dfs2(int node, int par, int curVal, int cur) {
	int ans = 1;
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i].first != par) {
			if(g[node][i].second <= curVal || g[node][i].second > cur) {
				continue;
			}
			else {
				ans += dfs2(g[node][i].first, node, g[node][i].second, cur);
			}
		}
	}
	return ans;
}

void Solve() {
	int n, q;
	cin >> n >> q;
	q += (n - 1);
	vector<pair<char, pair<int, int> > > queries;
	while(q--) {
		char c;
		cin >> c;
		int a, b;
		if(c == 'S') {
			cin >> a >> b;
			g[a].push_back({b, ++cnt});
			g[b].push_back({a, cnt});
		}
		else if(c == 'Q') {
			cin >> a >> b;
		}
		else {
			cin >> a;
			b = -1;
		}
		queries.push_back({c, {a, b}});
	}
	depth[1] = 0;
	g[1].push_back({-1, 0});
	isIncreasing[0][1] = -1;
	isDecreasing[0][1] = -1;
	dfs(1, -1);
	for(int i = 1; i < 20; i++) {
		for(int j = 1; j <= n; j++) {
			if(DP[i - 1][j] == -1) {
				DP[i][j] = -1;
			}
			else {
				DP[i][j] = DP[i - 1][DP[i - 1][j]];
			}
			if(DP[i][j] == -1) {
				isDecreasing[i][j] = -1;
				isIncreasing[i][j] = -1;
			}
			else {
				if(isDecreasing[i - 1][j] == -1 || isDecreasing[i - 1][DP[i - 1][j]] == -1) {
					isDecreasing[i][j] = -1;
				}
				else if(isDecreasing[i - 1][j] <= isDecreasing[0][DP[i - 1][j]]) {
					isDecreasing[i][j] = -1;
				}
				else {
					isDecreasing[i][j] = isDecreasing[i - 1][DP[i - 1][j]];
				}


				if(isIncreasing[i - 1][j] == -1 || isIncreasing[i - 1][DP[i - 1][j]] == -1) {
					isIncreasing[i][j] = -1;
				}
				else if(isIncreasing[i - 1][j] >= isIncreasing[0][DP[i - 1][j]]) {
					isIncreasing[i][j] = -1;
				}
				else {
					isIncreasing[i][j] = isIncreasing[i - 1][DP[i - 1][j]];
				}
			}
		}
	}
	/*for(int i = 0; i < 20; i++) {
		for(int j = 1; j <= n; j++) {
			cout << isIncreasing[i][j] << " ";
		}
		cout << "\n";
	}
	for(int i = 0; i < 20; i++) {
		for(int j = 1; j <= n; j++) {
			cout << isDecreasing[i][j] << " ";
		}
		cout << "\n";
	}*/
	cnt = 0;
	int val[n + 1];
	for(int i = 0; i <= n; i++) {
		val[i] = -1;
	}
	for(int i = 0; i < queries.size(); i++) {
		char c = queries[i].first;
		int a = queries[i].second.first, b = queries[i].second.second;
		if(c == 'S') {
			cnt++;
			if(a == 1)
				swap(a, b);
			val[a] = cnt - 1;
		}
		else if(c == 'Q') {
			if(Satisfied(a, b, cnt)) {
				cout << "yes\n";
			}
			else {
				cout << "no\n";
			}
		}
		else {
			if(a == 1) {
				cout << cnt + 1 << "\n";
			}
			else {
				if(val[a] == -1) {
					cout << "1\n";
				}
				else {
					cout << cnt - val[a] + 1 << "\n";
				}
			}
		}
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

servers.cpp: In function 'void dfs(long long int, long long int)':
servers.cpp:14:19: 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]
   14 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
servers.cpp: In function 'long long int dfs2(long long int, long long int, long long int, long long int)':
servers.cpp:93:19: 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(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
servers.cpp: In function 'void Solve()':
servers.cpp:187:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<char, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |  for(int i = 0; i < queries.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5