oj.uz

Submission #441771

# Submission time Handle Problem Language Result Execution time Memory
441771 2021-07-06T04:24:43 Z 8e7 Inside information (BOI21_servers) C++14
50 / 100
 512 ms 28416 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());
	//debug(cent);
	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, tc = 0;
	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;
			tc++;
			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);
	int act = 0;
	for (int i = 0;i < k;i++) {
		if (qtype[i]) cout << ans[i] << "\n", act++;
		else cout << (ans[i] ? "yes" : "no") << "\n";
	}
	assert(act == tc);
}
/*
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 34 ms 9676 KB Output is correct
2 Correct 48 ms 9848 KB Output is correct
3 Correct 46 ms 9740 KB Output is correct
4 Correct 48 ms 10060 KB Output is correct
5 Correct 49 ms 10228 KB Output is correct
6 Correct 45 ms 10036 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9676 KB Output is correct
2 Correct 48 ms 9848 KB Output is correct
3 Correct 46 ms 9740 KB Output is correct
4 Correct 48 ms 10060 KB Output is correct
5 Correct 49 ms 10228 KB Output is correct
6 Correct 45 ms 10036 KB Output is correct
7 Incorrect 35 ms 9348 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9680 KB Output is correct
2 Correct 217 ms 24116 KB Output is correct
3 Correct 212 ms 24144 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9680 KB Output is correct
2 Correct 217 ms 24116 KB Output is correct
3 Correct 212 ms 24144 KB Output is correct
4 Incorrect 35 ms 9340 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9556 KB Output is correct
2 Correct 405 ms 27092 KB Output is correct
3 Correct 383 ms 26936 KB Output is correct
4 Correct 320 ms 28220 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9556 KB Output is correct
2 Correct 405 ms 27092 KB Output is correct
3 Correct 383 ms 26936 KB Output is correct
4 Correct 320 ms 28220 KB Output is correct
5 Incorrect 35 ms 9432 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9584 KB Output is correct
2 Correct 317 ms 19556 KB Output is correct
3 Correct 357 ms 18292 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9584 KB Output is correct
2 Correct 317 ms 19556 KB Output is correct
3 Correct 357 ms 18292 KB Output is correct
4 Incorrect 35 ms 9408 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9616 KB Output is correct
2 Correct 400 ms 27168 KB Output is correct
3 Correct 431 ms 27024 KB Output is correct
4 Correct 326 ms 28232 KB Output is correct
5 Correct 34 ms 9588 KB Output is correct
6 Correct 315 ms 19692 KB Output is correct
7 Correct 322 ms 18296 KB Output is correct
8 Correct 313 ms 19200 KB Output is correct
9 Correct 371 ms 19108 KB Output is correct
10 Correct 512 ms 23592 KB Output is correct
11 Correct 409 ms 22112 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9616 KB Output is correct
2 Correct 400 ms 27168 KB Output is correct
3 Correct 431 ms 27024 KB Output is correct
4 Correct 326 ms 28232 KB Output is correct
5 Correct 34 ms 9588 KB Output is correct
6 Correct 315 ms 19692 KB Output is correct
7 Correct 322 ms 18296 KB Output is correct
8 Correct 313 ms 19200 KB Output is correct
9 Correct 371 ms 19108 KB Output is correct
10 Correct 512 ms 23592 KB Output is correct
11 Correct 409 ms 22112 KB Output is correct
12 Incorrect 33 ms 9420 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9660 KB Output is correct
2 Correct 48 ms 9924 KB Output is correct
3 Correct 45 ms 9816 KB Output is correct
4 Correct 59 ms 9972 KB Output is correct
5 Correct 49 ms 10304 KB Output is correct
6 Correct 46 ms 10044 KB Output is correct
7 Correct 34 ms 9672 KB Output is correct
8 Correct 220 ms 24048 KB Output is correct
9 Correct 209 ms 24052 KB Output is correct
10 Correct 35 ms 9540 KB Output is correct
11 Correct 418 ms 27064 KB Output is correct
12 Correct 367 ms 26980 KB Output is correct
13 Correct 321 ms 28416 KB Output is correct
14 Correct 35 ms 9600 KB Output is correct
15 Correct 296 ms 19616 KB Output is correct
16 Correct 313 ms 18324 KB Output is correct
17 Correct 360 ms 19136 KB Output is correct
18 Correct 413 ms 19112 KB Output is correct
19 Correct 456 ms 23440 KB Output is correct
20 Correct 426 ms 22112 KB Output is correct
21 Correct 247 ms 25148 KB Output is correct
22 Correct 294 ms 23188 KB Output is correct
23 Correct 296 ms 19096 KB Output is correct
24 Correct 278 ms 19152 KB Output is correct
25 Correct 372 ms 26256 KB Output is correct
26 Correct 351 ms 17596 KB Output is correct
27 Correct 323 ms 17768 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9660 KB Output is correct
2 Correct 48 ms 9924 KB Output is correct
3 Correct 45 ms 9816 KB Output is correct
4 Correct 59 ms 9972 KB Output is correct
5 Correct 49 ms 10304 KB Output is correct
6 Correct 46 ms 10044 KB Output is correct
7 Correct 34 ms 9672 KB Output is correct
8 Correct 220 ms 24048 KB Output is correct
9 Correct 209 ms 24052 KB Output is correct
10 Correct 35 ms 9540 KB Output is correct
11 Correct 418 ms 27064 KB Output is correct
12 Correct 367 ms 26980 KB Output is correct
13 Correct 321 ms 28416 KB Output is correct
14 Correct 35 ms 9600 KB Output is correct
15 Correct 296 ms 19616 KB Output is correct
16 Correct 313 ms 18324 KB Output is correct
17 Correct 360 ms 19136 KB Output is correct
18 Correct 413 ms 19112 KB Output is correct
19 Correct 456 ms 23440 KB Output is correct
20 Correct 426 ms 22112 KB Output is correct
21 Correct 247 ms 25148 KB Output is correct
22 Correct 294 ms 23188 KB Output is correct
23 Correct 296 ms 19096 KB Output is correct
24 Correct 278 ms 19152 KB Output is correct
25 Correct 372 ms 26256 KB Output is correct
26 Correct 351 ms 17596 KB Output is correct
27 Correct 323 ms 17768 KB Output is correct
28 Incorrect 34 ms 9412 KB Extra information in the output file
29 Halted 0 ms 0 KB -