oj.uz

Submission #447214

# Submission time Handle Problem Language Result Execution time Memory
447214 2021-07-25T06:43:05 Z hhhhaura Inside information (BOI21_servers) C++14
10 / 100
 3500 ms 53260 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;
		vprint(all(ch));
		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 40 ms 10428 KB Output is correct
2 Correct 153 ms 11928 KB Output is correct
3 Correct 85 ms 14668 KB Output is correct
4 Correct 176 ms 12740 KB Output is correct
5 Correct 180 ms 12988 KB Output is correct
6 Correct 55 ms 10548 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 10428 KB Output is correct
2 Correct 153 ms 11928 KB Output is correct
3 Correct 85 ms 14668 KB Output is correct
4 Correct 176 ms 12740 KB Output is correct
5 Correct 180 ms 12988 KB Output is correct
6 Correct 55 ms 10548 KB Output is correct
7 Correct 41 ms 11464 KB Output is correct
8 Correct 179 ms 16976 KB Output is correct
9 Correct 115 ms 18388 KB Output is correct
10 Correct 268 ms 18592 KB Output is correct
11 Correct 256 ms 18452 KB Output is correct
12 Correct 73 ms 14004 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9748 KB Output is correct
2 Correct 591 ms 37088 KB Output is correct
3 Correct 547 ms 36860 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 9748 KB Output is correct
2 Correct 591 ms 37088 KB Output is correct
3 Correct 547 ms 36860 KB Output is correct
4 Correct 38 ms 9968 KB Output is correct
5 Correct 590 ms 41868 KB Output is correct
6 Correct 610 ms 40868 KB Output is correct
7 Correct 673 ms 43152 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 11460 KB Output is correct
2 Execution timed out 3591 ms 53260 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 11460 KB Output is correct
2 Execution timed out 3591 ms 53260 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 11336 KB Output is correct
2 Execution timed out 3577 ms 42308 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 11336 KB Output is correct
2 Execution timed out 3577 ms 42308 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 10428 KB Output is correct
2 Correct 135 ms 11964 KB Output is correct
3 Correct 87 ms 14644 KB Output is correct
4 Correct 173 ms 12908 KB Output is correct
5 Correct 191 ms 13108 KB Output is correct
6 Correct 55 ms 10560 KB Output is correct
7 Correct 38 ms 9748 KB Output is correct
8 Correct 542 ms 36936 KB Output is correct
9 Correct 528 ms 36944 KB Output is correct
10 Correct 40 ms 11460 KB Output is correct
11 Execution timed out 3584 ms 53156 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 10428 KB Output is correct
2 Correct 135 ms 11964 KB Output is correct
3 Correct 87 ms 14644 KB Output is correct
4 Correct 173 ms 12908 KB Output is correct
5 Correct 191 ms 13108 KB Output is correct
6 Correct 55 ms 10560 KB Output is correct
7 Correct 38 ms 9748 KB Output is correct
8 Correct 542 ms 36936 KB Output is correct
9 Correct 528 ms 36944 KB Output is correct
10 Correct 40 ms 11460 KB Output is correct
11 Execution timed out 3584 ms 53156 KB Time limit exceeded
12 Halted 0 ms 0 KB -