oj.uz

Submission #447210

# Submission time Handle Problem Language Result Execution time Memory
447210 2021-07-25T06:22:47 Z hhhhaura Inside information (BOI21_servers) C++14
50 / 100
 745 ms 50224 KB 
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#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;
		ch.push_back(x);
		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;
		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));
				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:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
servers.cpp:24:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
servers.cpp:24:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | 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 36 ms 10384 KB Output is correct
2 Correct 51 ms 11932 KB Output is correct
3 Correct 62 ms 14636 KB Output is correct
4 Correct 56 ms 12616 KB Output is correct
5 Correct 54 ms 12856 KB Output is correct
6 Correct 42 ms 10568 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 10384 KB Output is correct
2 Correct 51 ms 11932 KB Output is correct
3 Correct 62 ms 14636 KB Output is correct
4 Correct 56 ms 12616 KB Output is correct
5 Correct 54 ms 12856 KB Output is correct
6 Correct 42 ms 10568 KB Output is correct
7 Incorrect 41 ms 11444 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 44 ms 9788 KB Output is correct
2 Correct 184 ms 36176 KB Output is correct
3 Correct 167 ms 36208 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 9788 KB Output is correct
2 Correct 184 ms 36176 KB Output is correct
3 Correct 167 ms 36208 KB Output is correct
4 Incorrect 39 ms 10024 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 40 ms 11564 KB Output is correct
2 Correct 745 ms 47308 KB Output is correct
3 Correct 733 ms 47564 KB Output is correct
4 Correct 446 ms 50224 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 11564 KB Output is correct
2 Correct 745 ms 47308 KB Output is correct
3 Correct 733 ms 47564 KB Output is correct
4 Correct 446 ms 50224 KB Output is correct
5 Incorrect 42 ms 11964 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 39 ms 11324 KB Output is correct
2 Correct 415 ms 35820 KB Output is correct
3 Correct 604 ms 36560 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 11324 KB Output is correct
2 Correct 415 ms 35820 KB Output is correct
3 Correct 604 ms 36560 KB Output is correct
4 Incorrect 41 ms 11320 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 39 ms 11536 KB Output is correct
2 Correct 712 ms 47260 KB Output is correct
3 Correct 693 ms 47664 KB Output is correct
4 Correct 425 ms 50204 KB Output is correct
5 Correct 37 ms 11324 KB Output is correct
6 Correct 404 ms 35916 KB Output is correct
7 Correct 631 ms 36652 KB Output is correct
8 Correct 668 ms 35952 KB Output is correct
9 Correct 682 ms 37348 KB Output is correct
10 Correct 745 ms 41600 KB Output is correct
11 Correct 702 ms 41016 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 11536 KB Output is correct
2 Correct 712 ms 47260 KB Output is correct
3 Correct 693 ms 47664 KB Output is correct
4 Correct 425 ms 50204 KB Output is correct
5 Correct 37 ms 11324 KB Output is correct
6 Correct 404 ms 35916 KB Output is correct
7 Correct 631 ms 36652 KB Output is correct
8 Correct 668 ms 35952 KB Output is correct
9 Correct 682 ms 37348 KB Output is correct
10 Correct 745 ms 41600 KB Output is correct
11 Correct 702 ms 41016 KB Output is correct
12 Incorrect 42 ms 11892 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 36 ms 10408 KB Output is correct
2 Correct 61 ms 11856 KB Output is correct
3 Correct 52 ms 14588 KB Output is correct
4 Correct 55 ms 12732 KB Output is correct
5 Correct 57 ms 12892 KB Output is correct
6 Correct 47 ms 10608 KB Output is correct
7 Correct 35 ms 9796 KB Output is correct
8 Correct 178 ms 36228 KB Output is correct
9 Correct 179 ms 36196 KB Output is correct
10 Correct 38 ms 11468 KB Output is correct
11 Correct 740 ms 47160 KB Output is correct
12 Correct 730 ms 47776 KB Output is correct
13 Correct 441 ms 50188 KB Output is correct
14 Correct 38 ms 11316 KB Output is correct
15 Correct 420 ms 35848 KB Output is correct
16 Correct 616 ms 36672 KB Output is correct
17 Correct 634 ms 36028 KB Output is correct
18 Correct 644 ms 37408 KB Output is correct
19 Correct 709 ms 41628 KB Output is correct
20 Correct 689 ms 41092 KB Output is correct
21 Correct 225 ms 37756 KB Output is correct
22 Correct 226 ms 36952 KB Output is correct
23 Correct 514 ms 39020 KB Output is correct
24 Correct 490 ms 38592 KB Output is correct
25 Correct 720 ms 42956 KB Output is correct
26 Correct 622 ms 34764 KB Output is correct
27 Correct 558 ms 34916 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 10408 KB Output is correct
2 Correct 61 ms 11856 KB Output is correct
3 Correct 52 ms 14588 KB Output is correct
4 Correct 55 ms 12732 KB Output is correct
5 Correct 57 ms 12892 KB Output is correct
6 Correct 47 ms 10608 KB Output is correct
7 Correct 35 ms 9796 KB Output is correct
8 Correct 178 ms 36228 KB Output is correct
9 Correct 179 ms 36196 KB Output is correct
10 Correct 38 ms 11468 KB Output is correct
11 Correct 740 ms 47160 KB Output is correct
12 Correct 730 ms 47776 KB Output is correct
13 Correct 441 ms 50188 KB Output is correct
14 Correct 38 ms 11316 KB Output is correct
15 Correct 420 ms 35848 KB Output is correct
16 Correct 616 ms 36672 KB Output is correct
17 Correct 634 ms 36028 KB Output is correct
18 Correct 644 ms 37408 KB Output is correct
19 Correct 709 ms 41628 KB Output is correct
20 Correct 689 ms 41092 KB Output is correct
21 Correct 225 ms 37756 KB Output is correct
22 Correct 226 ms 36952 KB Output is correct
23 Correct 514 ms 39020 KB Output is correct
24 Correct 490 ms 38592 KB Output is correct
25 Correct 720 ms 42956 KB Output is correct
26 Correct 622 ms 34764 KB Output is correct
27 Correct 558 ms 34916 KB Output is correct
28 Incorrect 40 ms 11452 KB Extra information in the output file
29 Halted 0 ms 0 KB -