제출 #659800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659800		NothingXD	Inside information (BOI21_servers)	C++17	5 / 100	204 ms	5156 KiB

servers

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

const int maxn = 1e4 + 10;
const int maxq = 2e5 + 10;
int n, q, N, h[maxn], cnt[maxn], ans[maxq];
int mark[maxq];
vector<pii> g[maxn];
vector<pii> Q2[maxn];
vector<pair<pii,int>> Q1[maxn];

void dfs(int v, int p = -1){
	for (auto [u, w]: g[v]){
		if (w > h[v]){
			h[u] = w;
			dfs(u, v);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n >> q;

	N = n + q;
	
	int tmp = 0;

	for (int i = 1; i < N; i++){
		char t; cin >> t;
		if (t == 'S'){
			tmp++;
			int u, v; cin >> u >> v;
			g[u].push_back({v, tmp});
			g[v].push_back({u, tmp});
		}
		else if (t == 'Q'){
			int x, y; cin >> x >> y;
			Q1[y].push_back({{tmp, x}, i});
			mark[i] = 1;
		}
		else{
			int x; cin >> x;
			Q2[x].push_back({tmp, i});
			mark[i] = 2;
		}
	}

	for (int i = 1; i <= n; i++){
		memset(cnt, 0, sizeof cnt);
		for (int j = 1; j <= n; j++) h[j] = n+1;
		h[i] = 0;
		dfs(i);
		for (int j = 1; j <= n; j++){
			cnt[h[j]]++;
		}
		for (int j = 1; j <= n; j++) cnt[j] += cnt[j-1];
		for (auto [x, t]: Q1[i]){
			if (h[x.S] <= x.F) ans[t] = 1;
		}
		for (auto [x, t]: Q2[i]){
			ans[t] = cnt[x];
		}
	}

	for (int i = 1; i < N; i++){
		if (mark[i] == 1) cout << (ans[i]? "yes\n": "no\n");
		else if (mark[i] == 2) cout << ans[i] << '\n';
	}

	return 0;
}

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