oj.uz

Submission #441773

# Submission time Handle Problem Language Result Execution time Memory
441773 2021-07-06T05:07:51 Z 8e7 Inside information (BOI21_servers) C++17
5 / 100
 3500 ms 26536 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <assert.h>
//#include <ext/pb_ds/assoc_contatiner.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) { cout << a << " ";debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << (*l) << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 120005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<pii> adj[maxn];
struct query{
	int ti, id, to;
	query() {ti = 0, id = 0, to = 0;}
	query(int x, int y, int z) {ti = x, id = y, to = z;}
};
vector<query> que[maxn];
int qtype[maxn], ans[maxn];

struct BIT{
	int bit[maxn];
	void modify(int ind, int val) {
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
	}
	int query(int ind) {
		int ret = 0;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret;
	}
} bit;
int siz[maxn];
bool mark[maxn];
int found[maxn];

void dfs(int n, int par) {
	siz[n] = 1;
	for (auto v:adj[n]) {
		if (v.ff != par && mark[v.ff]) {
			dfs(v.ff, n);
			siz[n] += siz[v.ff];
		}
	}
}
int get_centroid(int n, int par, int tot) {
	for (auto v:adj[n]) {
		if (v.ff != par && mark[v.ff]) {
			if (2 * siz[v.ff] >= tot) return get_centroid(v.ff, n, tot);
		}
	}	
	return n;
}

void get_node(int n, int par, int w, vector<pii> & ret, int dir) {
	ret.push_back({n, w});
	for (auto v:adj[n]) {
		if (v.ff != par && mark[v.ff] && (dir == 2 ? true : (dir ? v.ss > w : v.ss < w))) {
			get_node(v.ff, n, v.ss, ret, dir);
		}
	}
}
void recur(int n, int par, vector<int> & ret) {
	ret.push_back(n);
	for (auto v:adj[n]) {
		if (v.ff != par && mark[v.ff]) {
			recur(v.ff, n, ret);
		}
	}
}
void solve(vector<int> a) {
	//debug(49);
	//pary(a.begin(), a.end());
	for (int i:a) mark[i] = 1;
	dfs(a[0], 0);	
	vector<pii> op;
	int cent = get_centroid(a[0], 0, a.size());
	sort(adj[cent].begin(), adj[cent].end(), [&](pii x, pii y) {return x.ss > y.ss;});	
	for (auto v:adj[cent]) {
		if (!mark[v.ff]) continue;
		vector<pii> se;
		get_node(v.ff, cent, v.ss, se, 0);
		for (auto node:se) {
			//debug(7122, node.ff);
			for (auto q:que[node.ff]) {
				if (q.to == 0) {
					ans[q.id] += bit.query(q.ti) + 1;	
				} else if (mark[q.to]) {
					if (q.to != cent) ans[q.id] = (found[q.to] && found[q.to] <= q.ti);	
					else ans[q.id] = v.ss <= q.ti;
				}
			}
		}
		se.clear();
		get_node(v.ff, cent, v.ss, se, 1);
		for (auto node:se) {
			//debug(2217, node.ff);
			found[node.ff] = node.ss;
			bit.modify(node.ss, 1);
		}
		op.insert(op.end(), se.begin(), se.end());
	}
	for (auto q:que[cent]) {
		if (q.to == 0) {
			ans[q.id] += 1 + bit.query(q.ti);
		} else if (mark[q.to]){
			if (q.to == cent) ans[q.id] = 1;
			else ans[q.id] = found[q.to] && found[q.to] <= q.ti;
		}
	}
	for (auto i:op) {
		found[i.ff] = 0;
		bit.modify(i.ss, -1);
	}
	vector<vector<int> > rec;
	for (auto v:adj[cent]) {
		if (!mark[v.ff]) continue;
		vector<int> add;
		recur(v.ff, cent, add);
		rec.push_back(add);	
	}
	for (int i:a) mark[i] = 0;
	for (auto i:rec) solve(i);
}
int main() {
	io
	int n, k;
	cin >> n >> k;
	int cur = 1, qcnt = 0;
	for (int i = 1;i <= n;i++) mark[i] = 1;
	for (int i = 0;i < n + k - 1;i++) {
		char type;
		cin >> type;
		if (type == 'S') {
			int a, b;
			cin >> a >> b;
			adj[a].push_back({b, cur});
			adj[b].push_back({a, cur});
			cur++;
		} else if (type == 'Q') {
			int a, b;
			cin >> a >> b;
			qtype[qcnt] = 0;
			que[b].push_back(query(cur - 1, qcnt++, a));
		} else {
			int d;
			cin >> d;
			qtype[qcnt] = 1;
			que[d].push_back(query(cur - 1, qcnt++, 0));
		}
	}
	/*
	vector<int> st;
	for (int i = 1;i <= n;i++) st.push_back(i);
	solve(st);
	*/
	for (int i = 1;i <= n;i++) {
		vector<pii> it;
		get_node(i, 0, 0, it, 1);
		//for (auto p:it) cout << p.ff << " " << p.ss << endl;
		//cout << endl;
		for (auto q:que[i]) {
			if (q.to != 0) {
				for (auto p:it) {
					if (p.ff == q.to && p.ss <= q.ti) ans[q.id] = 1;
				}
			} else {
				for (auto p:it) {
					if (p.ss <= q.ti) ans[q.id]++;
				}
			}
		}
	}
	for (int i = 0;i < k;i++) {
		if (qtype[i]) cout << ans[i] << "\n";
		else cout << (ans[i] ? "yes" : "no") << "\n";
	}
}
/*
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
C 3
Q 5 1
C 6
Q 1 5
C 1
C 2
C 4
C 5

7 7
S 4 5
S 2 3
S 5 6
S 6 7
S 3 4
S 1 2
C 1
C 2
C 3
C 4
C 5
C 6
C 7
   */

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9540 KB Output is correct
2 Correct 46 ms 9596 KB Output is correct
3 Correct 87 ms 9612 KB Output is correct
4 Correct 46 ms 9488 KB Output is correct
5 Correct 44 ms 9628 KB Output is correct
6 Correct 437 ms 9796 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9540 KB Output is correct
2 Correct 46 ms 9596 KB Output is correct
3 Correct 87 ms 9612 KB Output is correct
4 Correct 46 ms 9488 KB Output is correct
5 Correct 44 ms 9628 KB Output is correct
6 Correct 437 ms 9796 KB Output is correct
7 Correct 35 ms 9284 KB Output is correct
8 Correct 47 ms 10848 KB Output is correct
9 Correct 147 ms 10416 KB Output is correct
10 Correct 45 ms 10832 KB Output is correct
11 Correct 43 ms 10812 KB Output is correct
12 Correct 671 ms 10692 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 9668 KB Output is correct
2 Execution timed out 3564 ms 16384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 9668 KB Output is correct
2 Execution timed out 3564 ms 16384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9552 KB Output is correct
2 Correct 164 ms 13948 KB Output is correct
3 Correct 157 ms 13812 KB Output is correct
4 Execution timed out 3567 ms 26396 KB Time limit exceeded

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9552 KB Output is correct
2 Correct 164 ms 13948 KB Output is correct
3 Correct 157 ms 13812 KB Output is correct
4 Execution timed out 3567 ms 26396 KB Time limit exceeded

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9528 KB Output is correct
2 Execution timed out 3574 ms 15424 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9528 KB Output is correct
2 Execution timed out 3574 ms 15424 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9552 KB Output is correct
2 Correct 171 ms 13808 KB Output is correct
3 Correct 170 ms 13764 KB Output is correct
4 Execution timed out 3554 ms 26536 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9552 KB Output is correct
2 Correct 171 ms 13808 KB Output is correct
3 Correct 170 ms 13764 KB Output is correct
4 Execution timed out 3554 ms 26536 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9588 KB Output is correct
2 Correct 45 ms 9604 KB Output is correct
3 Correct 92 ms 9488 KB Output is correct
4 Correct 46 ms 9536 KB Output is correct
5 Correct 44 ms 9624 KB Output is correct
6 Correct 441 ms 9984 KB Output is correct
7 Correct 38 ms 9764 KB Output is correct
8 Execution timed out 3575 ms 16296 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9588 KB Output is correct
2 Correct 45 ms 9604 KB Output is correct
3 Correct 92 ms 9488 KB Output is correct
4 Correct 46 ms 9536 KB Output is correct
5 Correct 44 ms 9624 KB Output is correct
6 Correct 441 ms 9984 KB Output is correct
7 Correct 38 ms 9764 KB Output is correct
8 Execution timed out 3575 ms 16296 KB Time limit exceeded
9 Halted 0 ms 0 KB -