Submission #528944

#	Time	Username	Problem	Language	Result	Execution time	Memory
528944		Arnch	Inside information (BOI21_servers)	C++17	100 / 100	708 ms	107896 KiB

servers

// oooo
/*
 be hengam shena mesle y dasto pa cholofti ~
 bepa to masire dahane koose neyofti ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

// fen[0] -> soodi
// fen[1] -> nozoli 

struct node {
	int up, down;
	bool f;
	node() {
		up = down = f = 0;
	}
};
int n, k, t, r, hide[N], sz[N], h[N], u[N], v[N], ans[N], fen[N];
node cnt[N];
char type[N];
vector<int> con[N], his, A, B; vector<pair<int, int> > G[N], query[N];

bool cmp(pair<int, int> p1, pair<int, int> p2) {
	return p1.second > p2.second;
}
void get_input() {
	cin >>n >>k;
	for(int i = 1; i < n + k; i++) {
		cin >>type[i];
		if(type[i] != 'C') {
			cin >>u[i] >>v[i], u[i]--, v[i]--;
			if(type[i] == 'S') 
				G[u[i]].push_back({v[i], i}), G[v[i]].push_back({u[i], i});
			else
				query[u[i]].push_back({v[i], i});
			continue;
		}	
		cin >>u[i], u[i]--;
		con[u[i]].push_back(i);
	}
	for(int i = 0; i < n; i++) 
		sort(All(G[i]), cmp);
}

void upd(int ind, int val) {
	for(++ind; ind < N; ind += ind & -ind) {
		fen[ind] += val;
		his.push_back(ind);
	}
}
int get(int ind) {
	int sum = 0;
	for(++ind; ind; ind -= ind & -ind) {
		sum += fen[ind];
	}
	return sum;
}

void plant(int x, int p = -1) {
	sz[x] = 1;
	for(auto &i : G[x]) {
		if(i.first == p || hide[i.first]) continue;
		plant(i.first, x);
		sz[x] += sz[i.first];
	}
}
int get_centroid(int x, int _n, int p = -1) {
	for(auto &i : G[x]) {
		if(i.first == p || hide[i.first]) continue;
		if(2 * sz[i.first] > _n) return get_centroid(i.first, _n, x);
	}
	return x;
}
void DFS0(int x, int p = -1) {
	for(auto &i : G[x]) {
		if(i.first == p || hide[i.first]) continue;
		if(i.second <= cnt[x].down && cnt[x].down <= cnt[x].up && cnt[x].f == 1) {
			cnt[i.first].f = 1;
			cnt[i.first].down = i.second;
			if(p == -1) cnt[i.first].up = i.second;
			else cnt[i.first].up = cnt[x].up;
		}
		else if(i.second >= cnt[x].down && cnt[x].down >= cnt[x].up && cnt[x].f == 1) {
			cnt[i.first].f = 1;
			cnt[i.first].down = i.second;
			if(p == -1) cnt[i.first].up = i.second;
			else cnt[i.first].up = cnt[x].up;
		}
		else {
			cnt[i.first].f = 0;
		}
		DFS0(i.first, x);
	}
	if(x != r) B.push_back(x);
}
void DFS1(int x, int p = -1) {
	if(x != r && cnt[x].f == 1) {
		for(auto &i : query[x]) {
			if(cnt[i.first].f == 0 || hide[i.first]) continue;
			if(i.first == r) {
				if(cnt[x].up <= cnt[x].down && i.second >= cnt[x].down) {
					ans[i.second] = 1;
				}
				continue;
			}
			if(cnt[i.first].up >= cnt[i.first].down && cnt[i.first].up <= cnt[x].up && cnt[x].up <= cnt[x].down && i.second >= cnt[x].down) {
				ans[i.second] = 1;
			}
		}
	}
	for(auto &i : G[x]) {
		if(hide[i.first] || i.first == p) continue;
		DFS1(i.first, x);
	}
	for(auto &i : con[x]) {
		if(cnt[x].f == 1 && cnt[x].up >= cnt[x].down && cnt[x].up <= i) {
			ans[i]++;
		}
	}
}
void DFS2(int x, int p = -1) {
	if(x != r && cnt[x].f == 1 && cnt[x].up >= cnt[x].down) {
		for(auto &i : con[x]) {
			ans[i] += get(i);
		}
	}
	if(x != r) A.push_back(x);
	for(auto &i : G[x]) {
		if(i.first == p || hide[i.first]) continue;
		DFS2(i.first, x);
	}
}
void solve(int x) {
	h[x] = 0, cnt[x].f = 1, DFS0(x);
	DFS1(x);
	for(auto &i : query[x]) {
		if(cnt[i.first].f == 0 || hide[i.first]) continue;
		if(cnt[i.first].up >= cnt[i.first].down && i.second >= cnt[i.first].up) {
			ans[i.second] = 1;
		}
	}	
	for(auto &i : G[x]) {
		if(hide[i.first]) continue;
		DFS2(i.first, x);
		for(auto &j : A) {
			if(cnt[j].f == 1 && cnt[j].up <= cnt[j].down) upd(cnt[j].down, 1);
		}
		A.clear();
	}
	for(auto &i : con[x]) {
		ans[i] += get(i);
	}

	for(auto &i : his) fen[i] = 0;
	his.clear();
	for(auto &i : B) cnt[i].up = cnt[i].down = cnt[i].f = 0;
	B.clear();
}
void decompose(int x) {
	plant(x);
	r = get_centroid(x, sz[x]);
	solve(r), hide[r] = 1;
	for(auto &i : G[r]) {
		if(hide[i.first]) continue;
		decompose(i.first);
	}
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);
	
	get_input();

	decompose(0);

	for(int i = 1; i < n + k; i++) {
		if(type[i] == 'S') continue;
		if(type[i] == 'Q') {
			(ans[i] == 1) ? (cout<<"yes\n") : (cout<<"no\n");
		}
		else {
			cout<<ans[i] <<'\n';
		}
	}

    return 0;
}

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