oj.uz

Submission #447215

# Submission time Handle Problem Language Result Execution time Memory
447215 2021-07-25T06:43:43 Z hhhhaura Inside information (BOI21_servers) C++14
100 / 100
 1123 ms 90428 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define wiwihorz
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i --)
#define ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()

#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)

using namespace std;

#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19938 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) cerr << "Line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); }
#else
#define print(...) 0
#define vprint(...) 0
#endif
struct BIT {
	int n;
	vector<int> v;
	stack<pii> ops;
	void init_(int _n) {
		n = _n;
		v.assign(n + 1, 0);
	}
	int lowbit(int x) { return x & (-x); }
	void modify(int x, int val) {
		if(x == 0) return;
		if(val > 0) ops.push({x, val});
		for(int i = x; i <= n; i += lowbit(i)) {
			v[i] += val;
		}
	}
	int query(int x) {
		int ans = 0;
		for(int i = x; i > 0; i -= lowbit(i)) {
			ans += v[i];
		}
		return ans;
	}
	int ask(int x) {
		return query(n) - query(x - 1);
	}
	void undo() {
		while(ops.size()) {
			pii cur = ops.top(); ops.pop();
			modify(cur.first, -cur.second);
		}
	}
};

namespace solver {
	int n, k;
	BIT bit;
	vector<int> vis, mx, sz, R, ch;
	vector<int> L, J, es, cost, t, ans, tp;
	vector<pii> a;
	vector<vector<pii>> nxt;
	vector<vector<int>> mp;
	void init_(int _n, int _k) {
		n = _n, k = _k;
		bit.init_(n + k);
		vis.assign(n + 1, 0);
		mx.assign(n + 1, 0);
		sz.assign(n + 1, 0);
		R.assign(n + 1, 0);
		L.assign(n + 1, 0);
		J.assign(n + 1, 0);
		
		es.assign(1, 0);
		cost.assign(1, INF);
		ch.clear();
		
		tp.assign(k + 1, 0);
		a.assign(k + 1, {0, 0});
		ans.assign(k + 1, 0);
		t.assign(k + 1, 0);
		nxt.assign(n + 1, vector<pii>());
		mp.assign(n + 1, vector<int>());
	}
	void add_edge(int a, int b, int c) {
		mp[a].push_back(es.size());
		mp[b].push_back(es.size());
		es.push_back(a ^ b);
		cost.push_back(c);
	}
	void get_sz(int x, int par) {
		mx[x] = 0, sz[x] = 1;
		for(auto i : mp[x]) if(i != par) {
			int to = es[i] ^ x;
			if(vis[to]) continue;
			get_sz(to, i);
			sz[x] += sz[to];
			mx[x] = max(mx[x], sz[to]);
		}
	}
	int get_cen(int x, int par, int tot) {
		int best = x;
		for(auto i : mp[x]) if(i != par) {
			int to = es[i] ^ x;
			if(vis[to]) continue;
			int cur = get_cen(to, i, tot);
			if(max(mx[cur], tot - sz[cur]) < 
				max(mx[best], tot - sz[best])) best = cur;
		}
		return best;
	}
	void dfs(int x, int par, int l, int j, int r) {
		J[x] = j, L[x] = l, R[x] = r;
		ch.push_back(x);
		for(auto i : mp[x]) if(i != par) {
			int to = es[i] ^ x;
			if(vis[to]) continue;
			dfs(to, i, l,
				(cost[par] > cost[i] ? j : INF), 
				(cost[par] < cost[i] ? max(cost[i], r) : INF)
			);
		}
	}
	void deco(int x, vector<pii> q) {
		ch.clear();
		get_sz(x, -1);
		int c = get_cen(x, -1, sz[x]);
		vis[c] = 1;
		R[c] = J[c] = L[c] = 0;
		vector<vector<pii>> temp(mp[c].size(), vector<pii>());
		for(auto i : mp[c]) {
			int to = es[i] ^ c;
			if(vis[to]) continue;
			nxt[i].clear();
			dfs(to, i, i, cost[i], cost[i]);
		}
		vector<pii> s;
		for(auto i : q) {
			if(i.first == 1) {
				int x, y; tie(x, y) = a[i.second];
				if(L[x] == L[y]) nxt[L[x]].push_back(i);
				else if(x == c) ans[i.second] = (t[i.second] > J[y]);	
				else if(y == c) ans[i.second] = (t[i.second] > R[x]);	
				else ans[i.second] = (J[y] < cost[L[x]] && t[i.second] > R[x]);	
			}
			else s.push_back({0, i.second});
		}
		for(auto i : ch) s.push_back({1, i});
		sort(all(s), [](pii a, pii b) {
			int t1 = (a.first? R[a.second] : t[a.second]);
			int t2 = (b.first? R[b.second] : t[b.second]);
			return t1 < t2;
		});			 
		for(auto i : s) {
			if(i.first) bit.modify(min(n + k, cost[L[i.second]]), 1);
			else {
				int x = a[i.second].first;
				ans[i.second] += bit.ask(min(J[x] + 1, n + k + 1)) + (J[x] < t[i.second]);
				if(x != c) nxt[L[x]].push_back({2, i.second});
			}
 		}
		bit.undo();
		rep(i, 0, signed(mp[c].size()) - 1) {
			temp[i].swap(nxt[mp[c][i]]);
		}
		rep(i, 0, signed(mp[c].size()) - 1) {
			int e = mp[c][i], to = es[e] ^ c;
			if(vis[to]) continue;
			deco(to, temp[i]);
		}
		return;
	}
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, k, cur = 0; 
	cin >> n >> k;
	init_(n, k);
	vector<pii> q;
	rep(i, 1, n + k - 1) {
		char c; cin >> c;
		if(c == 'S') {
			int x, y; cin >> x >> y;
			add_edge(x, y, i);
		}
		else if(c == 'Q') {
			int x, y; cin >> x >> y;
			a[++cur] = {x, y};
			tp[cur] = 1, t[cur] = i;
			if(x == y) ans[cur] = 1;
			else q.push_back({1, cur});
		}
		else {
			int x; cin >> x;
			a[++cur] = {x, -1};
			tp[cur] = 2, t[cur] = i;
			q.push_back({2, cur});
		} 
	}
	deco(1, q);
	rep(i, 1, k) {
		if(tp[i] == 1) cout << (ans[i] ? "yes" : "no") << "\n";
		else cout << ans[i] << "\n";
	}
	return 0;
}
/*
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6
*/

Compilation message

servers.cpp:3: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    3 | #pragma loop-opt(on)
      | 
servers.cpp:23:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
servers.cpp:23:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 10356 KB Output is correct
2 Correct 52 ms 11964 KB Output is correct
3 Correct 51 ms 14620 KB Output is correct
4 Correct 54 ms 12504 KB Output is correct
5 Correct 56 ms 12852 KB Output is correct
6 Correct 43 ms 10560 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 10356 KB Output is correct
2 Correct 52 ms 11964 KB Output is correct
3 Correct 51 ms 14620 KB Output is correct
4 Correct 54 ms 12504 KB Output is correct
5 Correct 56 ms 12852 KB Output is correct
6 Correct 43 ms 10560 KB Output is correct
7 Correct 41 ms 11384 KB Output is correct
8 Correct 103 ms 15680 KB Output is correct
9 Correct 80 ms 17120 KB Output is correct
10 Correct 135 ms 17356 KB Output is correct
11 Correct 129 ms 17152 KB Output is correct
12 Correct 59 ms 12948 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9856 KB Output is correct
2 Correct 168 ms 36188 KB Output is correct
3 Correct 167 ms 36220 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9856 KB Output is correct
2 Correct 168 ms 36188 KB Output is correct
3 Correct 167 ms 36220 KB Output is correct
4 Correct 36 ms 10028 KB Output is correct
5 Correct 209 ms 38516 KB Output is correct
6 Correct 235 ms 38424 KB Output is correct
7 Correct 224 ms 40320 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11460 KB Output is correct
2 Correct 710 ms 47252 KB Output is correct
3 Correct 690 ms 47740 KB Output is correct
4 Correct 434 ms 50172 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11460 KB Output is correct
2 Correct 710 ms 47252 KB Output is correct
3 Correct 690 ms 47740 KB Output is correct
4 Correct 434 ms 50172 KB Output is correct
5 Correct 43 ms 11924 KB Output is correct
6 Correct 822 ms 54244 KB Output is correct
7 Correct 554 ms 56508 KB Output is correct
8 Correct 956 ms 56048 KB Output is correct
9 Correct 944 ms 56052 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11460 KB Output is correct
2 Correct 405 ms 35928 KB Output is correct
3 Correct 597 ms 36540 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11460 KB Output is correct
2 Correct 405 ms 35928 KB Output is correct
3 Correct 597 ms 36540 KB Output is correct
4 Correct 41 ms 11428 KB Output is correct
5 Correct 565 ms 41812 KB Output is correct
6 Correct 755 ms 42432 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11524 KB Output is correct
2 Correct 720 ms 47116 KB Output is correct
3 Correct 709 ms 47632 KB Output is correct
4 Correct 454 ms 50192 KB Output is correct
5 Correct 38 ms 11324 KB Output is correct
6 Correct 406 ms 36076 KB Output is correct
7 Correct 645 ms 36520 KB Output is correct
8 Correct 648 ms 36136 KB Output is correct
9 Correct 659 ms 37392 KB Output is correct
10 Correct 710 ms 41628 KB Output is correct
11 Correct 687 ms 41076 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11524 KB Output is correct
2 Correct 720 ms 47116 KB Output is correct
3 Correct 709 ms 47632 KB Output is correct
4 Correct 454 ms 50192 KB Output is correct
5 Correct 38 ms 11324 KB Output is correct
6 Correct 406 ms 36076 KB Output is correct
7 Correct 645 ms 36520 KB Output is correct
8 Correct 648 ms 36136 KB Output is correct
9 Correct 659 ms 37392 KB Output is correct
10 Correct 710 ms 41628 KB Output is correct
11 Correct 687 ms 41076 KB Output is correct
12 Correct 41 ms 11920 KB Output is correct
13 Correct 849 ms 54256 KB Output is correct
14 Correct 545 ms 56600 KB Output is correct
15 Correct 961 ms 56128 KB Output is correct
16 Correct 972 ms 56036 KB Output is correct
17 Correct 41 ms 12244 KB Output is correct
18 Correct 552 ms 41872 KB Output is correct
19 Correct 727 ms 42404 KB Output is correct
20 Correct 890 ms 43608 KB Output is correct
21 Correct 840 ms 44460 KB Output is correct
22 Correct 987 ms 50972 KB Output is correct
23 Correct 1123 ms 47364 KB Output is correct
24 Correct 909 ms 45608 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 10376 KB Output is correct
2 Correct 49 ms 11808 KB Output is correct
3 Correct 51 ms 14584 KB Output is correct
4 Correct 55 ms 12496 KB Output is correct
5 Correct 57 ms 12912 KB Output is correct
6 Correct 44 ms 10584 KB Output is correct
7 Correct 35 ms 9796 KB Output is correct
8 Correct 171 ms 36284 KB Output is correct
9 Correct 170 ms 36236 KB Output is correct
10 Correct 38 ms 11520 KB Output is correct
11 Correct 712 ms 47064 KB Output is correct
12 Correct 707 ms 47520 KB Output is correct
13 Correct 445 ms 50144 KB Output is correct
14 Correct 37 ms 11324 KB Output is correct
15 Correct 411 ms 35872 KB Output is correct
16 Correct 614 ms 36460 KB Output is correct
17 Correct 612 ms 36032 KB Output is correct
18 Correct 646 ms 37276 KB Output is correct
19 Correct 722 ms 41708 KB Output is correct
20 Correct 712 ms 41116 KB Output is correct
21 Correct 221 ms 37728 KB Output is correct
22 Correct 210 ms 36740 KB Output is correct
23 Correct 459 ms 38944 KB Output is correct
24 Correct 467 ms 38740 KB Output is correct
25 Correct 687 ms 43164 KB Output is correct
26 Correct 565 ms 34464 KB Output is correct
27 Correct 556 ms 35092 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 10376 KB Output is correct
2 Correct 49 ms 11808 KB Output is correct
3 Correct 51 ms 14584 KB Output is correct
4 Correct 55 ms 12496 KB Output is correct
5 Correct 57 ms 12912 KB Output is correct
6 Correct 44 ms 10584 KB Output is correct
7 Correct 35 ms 9796 KB Output is correct
8 Correct 171 ms 36284 KB Output is correct
9 Correct 170 ms 36236 KB Output is correct
10 Correct 38 ms 11520 KB Output is correct
11 Correct 712 ms 47064 KB Output is correct
12 Correct 707 ms 47520 KB Output is correct
13 Correct 445 ms 50144 KB Output is correct
14 Correct 37 ms 11324 KB Output is correct
15 Correct 411 ms 35872 KB Output is correct
16 Correct 614 ms 36460 KB Output is correct
17 Correct 612 ms 36032 KB Output is correct
18 Correct 646 ms 37276 KB Output is correct
19 Correct 722 ms 41708 KB Output is correct
20 Correct 712 ms 41116 KB Output is correct
21 Correct 221 ms 37728 KB Output is correct
22 Correct 210 ms 36740 KB Output is correct
23 Correct 459 ms 38944 KB Output is correct
24 Correct 467 ms 38740 KB Output is correct
25 Correct 687 ms 43164 KB Output is correct
26 Correct 565 ms 34464 KB Output is correct
27 Correct 556 ms 35092 KB Output is correct
28 Correct 41 ms 11452 KB Output is correct
29 Correct 98 ms 16864 KB Output is correct
30 Correct 79 ms 18268 KB Output is correct
31 Correct 133 ms 18468 KB Output is correct
32 Correct 127 ms 18184 KB Output is correct
33 Correct 61 ms 14004 KB Output is correct
34 Correct 37 ms 10828 KB Output is correct
35 Correct 214 ms 41128 KB Output is correct
36 Correct 222 ms 40084 KB Output is correct
37 Correct 221 ms 42352 KB Output is correct
38 Correct 42 ms 12732 KB Output is correct
39 Correct 854 ms 54276 KB Output is correct
40 Correct 546 ms 56568 KB Output is correct
41 Correct 956 ms 55964 KB Output is correct
42 Correct 973 ms 56104 KB Output is correct
43 Correct 41 ms 12220 KB Output is correct
44 Correct 547 ms 41908 KB Output is correct
45 Correct 734 ms 42436 KB Output is correct
46 Correct 892 ms 43760 KB Output is correct
47 Correct 823 ms 44452 KB Output is correct
48 Correct 1018 ms 50764 KB Output is correct
49 Correct 1087 ms 47372 KB Output is correct
50 Correct 895 ms 45604 KB Output is correct
51 Correct 238 ms 45084 KB Output is correct
52 Correct 226 ms 43124 KB Output is correct
53 Correct 239 ms 42960 KB Output is correct
54 Correct 231 ms 41244 KB Output is correct
55 Correct 238 ms 50280 KB Output is correct
56 Correct 561 ms 49720 KB Output is correct
57 Correct 841 ms 90428 KB Output is correct
58 Correct 861 ms 44152 KB Output is correct
59 Correct 620 ms 39240 KB Output is correct