oj.uz

Submission #586923

# Submission time Handle Problem Language Result Execution time Memory
586923 2022-07-01T04:30:30 Z pavement Inside information (BOI21_servers) C++17
100 / 100
 2062 ms 178256 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, K, cent, tot_sz, sz[240005], A[240005], B[240005], inc[240005], down[240005], dep[240005], par[240005], anc[25][240005], wei[25][240005];
bool vis[240005];
char C[240005];
vector<int> disc_1[240005], disc_2[240005];
vector<ii> adj[240005], vec[240005];

template <class T>
struct wavelet_matrix {
    using size_type = uint32_t;
    struct bit_vector {
        static constexpr size_type wsize = 64;
        static size_type rank64(uint64_t x, size_type i) {
            return __builtin_popcountll(x & ((1ULL << i) - 1));
        }
#pragma pack(4)
        struct block_t {
            uint64_t bit;
            size_type sum;
        };
#pragma pack()
        size_type n, zeros;
        vector<block_t> block;
        bit_vector(size_type _n = 0) : n(_n), block(n / wsize + 1) {}
        int operator[](size_type i) const {
            return block[i / wsize].bit >> i % wsize & 1;
        }
        void set(size_type i) {
            block[i / wsize].bit |= (uint64_t)1 << i % wsize;
        }
        void build() {
            for (size_type j = 0; j < n / wsize; ++j)
                block[j + 1].sum =
                    block[j].sum + __builtin_popcountll(block[j].bit);
            zeros = rank0(n);
        }
        size_type rank0(size_type i) const { return i - rank1(i); }
        size_type rank1(size_type i) const {
            auto&& e = block[i / wsize];
            return e.sum + rank64(e.bit, i % wsize);
        }
    };
    size_type n, lg;
    vector<T> a;
    vector<bit_vector> bv;
    wavelet_matrix(size_type _n = 0) : n(_n), a(n) {}
    wavelet_matrix(const vector<T>& _a) : n(_a.size()), a(_a) { build(); }
    T& operator[](size_type i) { return a[i]; }
    void build() {
        lg = __lg(max<T>(
                 *max_element(begin(a), end(a)), 1)) +
             1;
        bv.assign(lg, n);
        vector<T> cur = a, nxt(n);
        for (auto h = lg; h--;) {
            for (size_type i = 0; i < n; ++i)
                if (cur[i] >> h & 1) bv[h].set(i);
            bv[h].build();
            array it{begin(nxt), begin(nxt) + bv[h].zeros};
            for (size_type i = 0; i < n; ++i) *it[bv[h][i]]++ = cur[i];
            swap(cur, nxt);
        }
    }
    // find kth element in [l, r), 0 indexed
    T kth(size_type l, size_type r, size_type k) const {
        T res = 0;
        for (auto h = lg; h--;) {
            auto l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
            if (k < r0 - l0)
                l = l0, r = r0;
            else {
                k -= r0 - l0;
                res |= (T)1 << h;
                l += bv[h].zeros - l0;
                r += bv[h].zeros - r0;
            }
        }
        return res;
    }
    // count i in [l..r) satisfying a[i] < ub
    size_type count(size_type l, size_type r, T ub) const {
        if (ub >= (T)1 << lg) return r - l;
        size_type res = 0;
        for (auto h = lg; h--;) {
            auto l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
            if (~ub >> h & 1)
                l = l0, r = r0;
            else {
                res += r0 - l0;
                l += bv[h].zeros - l0;
                r += bv[h].zeros - r0;
            }
        }
        return res;
    }
    size_type count(size_type l, size_type r, T lb, T ub) const {
        return count(l, r, ub) - count(l, r, lb);
    }
};

wavelet_matrix<int> wm[240005];

template <class T>
auto zip(const vector<T>& a) {
    int n = size(a);
    vector<pair<T, int>> p(n);
    for (int i = 0; i < n; ++i) p[i] = {a[i], i};
    sort(begin(p), end(p));
    vector<int> na(n);
    vector<T> v;
    for (int k = 0, rnk = -1; k < n; ++k) {
        if (k == 0 or p[k - 1].first < p[k].first)
            v.push_back(p[k].first), ++rnk;
        na[p[k].second] = rnk;
    }
    return make_pair(na, v);
}

int get_sizes(int n, int e = -1) {
	sz[n] = 1;
	for (auto [u, w] : adj[n]) if (u != e && !vis[u])
		sz[n] += get_sizes(u, n);
	return sz[n];
}

void get_centroid(int n, int e = -1) {
	int m = tot_sz - sz[n];
	for (auto [u, w] : adj[n]) if (u != e && !vis[u]) {
		get_centroid(u, n);
		m = max(m, sz[u]);
	}
	if (m <= tot_sz / 2) cent = n;
}

void dfs(int n, int e = -1, int prv = -1) {
	anc[0][n] = e;
	wei[0][n] = prv;
	for (int k = 1; k < 20; k++)
		if (anc[k - 1][n] != -1) {
			anc[k][n] = anc[k - 1][anc[k - 1][n]];
			wei[k][n] = max(wei[k - 1][n], wei[k - 1][anc[k - 1][n]]);
		}
	for (auto [u, w] : adj[n]) if (u != e) {
		dep[u] = dep[n] + 1;
		if (w < prv) inc[u] = inc[n], down[u] = n;
		else down[u] = down[n], inc[u] = n;
		dfs(u, n, w);
	}
}

bool qry(int u, int v, int t) {
	int ou = u, ov = v, m_w = 0;
	bool has_swap = 0;
	if (dep[u] > dep[v]) {
		swap(u, v);
		has_swap = 1;
	}
	for (int k = 19; k >= 0; k--)
		if (dep[v] - (1 << k) >= dep[u]) {
			m_w = max(m_w, wei[k][v]);
			v = anc[k][v];
		}
	if (u == v) {
		if (m_w > t) return 0;
		if (dep[ou] <= dep[ov]) return dep[down[ov]] <= dep[ou];
		else return dep[inc[ou]] <= dep[ov];
	}
	if (has_swap) swap(u, v);
	for (int k = 19; k >= 0; k--)
		if (anc[k][u] != anc[k][v]) {
			m_w = max({m_w, wei[k][u], wei[k][v]});
			u = anc[k][u];
			v = anc[k][v];
		}
	int lca = anc[0][u];
	m_w = max({m_w, wei[0][u], wei[0][v]});
	return m_w < t && dep[inc[ou]] <= dep[lca] && dep[down[ov]] <= dep[lca] && wei[0][u] < wei[0][v];
}

ii get_ends(int u, int v) {
	int ou = u, ov = v;
	bool has_swap = 0;
	assert(u != v);
	if (dep[u] > dep[v]) {
		swap(u, v);
		has_swap = 1;
	}
	for (int k = 19; k >= 0; k--)
		if (dep[v] - (1 << k) >= dep[u] + 1) v = anc[k][v];
	if (u == anc[0][v]) {
		auto ret = mp(wei[0][v], wei[0][has_swap ? ou : ov]);
		if (has_swap) swap(ret.first, ret.second);
		return ret;
	}
	auto ret = mp(wei[0][ou], wei[0][ov]);
	return ret;
}

void decomp(int n, int e = -1) {
	get_sizes(n);
	tot_sz = sz[n];
	cent = -1;
	get_centroid(n);
	assert(cent != -1);
	vis[cent] = 1;
	par[cent] = e;
	int orig_cent = cent;
	for (auto [u, w] : adj[cent]) if (!vis[u])
		decomp(u, orig_cent);
}

int qq(int x, int l, int r) {
	int st = upper_bound(disc_1[x].begin(), disc_1[x].end(), l) - disc_1[x].begin(), ub = lower_bound(disc_2[x].begin(), disc_2[x].end(), r) - disc_2[x].begin();
	return wm[x].count(st, disc_1[x].size(), ub);
}

main() {
	memset(anc, -1, sizeof anc);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N + K - 1; i++) {
		cin >> C[i];
		if (C[i] == 'S' || C[i] == 'Q') cin >> A[i] >> B[i];
		else cin >> A[i];
		if (C[i] == 'S') {
			adj[A[i]].eb(B[i], i);
			adj[B[i]].eb(A[i], i);
		}
	}
	inc[1] = down[1] = 1;
	dfs(1);
	decomp(1);
	for (int i = 1; i <= N; i++) {
		for (int u = par[i]; u != -1; u = par[u]) {
			if (qry(u, i, (int)1e9)) {
				auto curr = get_ends(u, i);
				vec[u].eb(curr.first, curr.second);
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		if (vec[i].empty()) continue;
		for (auto [x, y] : vec[i]) disc_1[i].pb(x);
		sort(disc_1[i].begin(), disc_1[i].end());
		sort(vec[i].begin(), vec[i].end());
		vector<int> vals;
		for (auto [x, y] : vec[i]) vals.pb(y);
		auto [na, v] = zip(vals);
		copy(vals.begin(), vals.end(), back_inserter(disc_2[i]));
		sort(disc_2[i].begin(), disc_2[i].end());
		wm[i] = wavelet_matrix(na);
	}
	for (int i = 1; i <= N + K - 1; i++) {
		if (C[i] == 'Q') {
			if (qry(B[i], A[i], i)) cout << "yes\n";
			else cout << "no\n";
		} else if (C[i] == 'C') {
			int ans = 1 + qq(A[i], (int)-1e9, i);
			for (int u = par[A[i]]; u != -1; u = par[u]) {
				if (qry(A[i], u, i)) {
					auto curr = get_ends(A[i], u);
					ans += 1 + qq(u, curr.second, i);
				}
			}
			cout << ans << '\n';
		}
	}
}

Compilation message

servers.cpp:244:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  244 | main() {
      | ^~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 64 ms 85652 KB Output is correct
2 Correct 85 ms 86844 KB Output is correct
3 Correct 71 ms 86704 KB Output is correct
4 Correct 90 ms 87244 KB Output is correct
5 Correct 81 ms 87492 KB Output is correct
6 Correct 66 ms 86532 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 64 ms 85652 KB Output is correct
2 Correct 85 ms 86844 KB Output is correct
3 Correct 71 ms 86704 KB Output is correct
4 Correct 90 ms 87244 KB Output is correct
5 Correct 81 ms 87492 KB Output is correct
6 Correct 66 ms 86532 KB Output is correct
7 Correct 65 ms 85604 KB Output is correct
8 Correct 111 ms 86912 KB Output is correct
9 Correct 95 ms 86668 KB Output is correct
10 Correct 145 ms 87244 KB Output is correct
11 Correct 138 ms 87344 KB Output is correct
12 Correct 86 ms 86604 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 85692 KB Output is correct
2 Correct 239 ms 109760 KB Output is correct
3 Correct 249 ms 109796 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 85692 KB Output is correct
2 Correct 239 ms 109760 KB Output is correct
3 Correct 249 ms 109796 KB Output is correct
4 Correct 67 ms 85764 KB Output is correct
5 Correct 254 ms 109776 KB Output is correct
6 Correct 217 ms 111540 KB Output is correct
7 Correct 199 ms 111660 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 85660 KB Output is correct
2 Correct 491 ms 142168 KB Output is correct
3 Correct 500 ms 142132 KB Output is correct
4 Correct 639 ms 177284 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 85660 KB Output is correct
2 Correct 491 ms 142168 KB Output is correct
3 Correct 500 ms 142132 KB Output is correct
4 Correct 639 ms 177284 KB Output is correct
5 Correct 64 ms 85684 KB Output is correct
6 Correct 823 ms 142088 KB Output is correct
7 Correct 1031 ms 175296 KB Output is correct
8 Correct 980 ms 141932 KB Output is correct
9 Correct 971 ms 142056 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 85568 KB Output is correct
2 Correct 501 ms 149996 KB Output is correct
3 Correct 396 ms 124892 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 85568 KB Output is correct
2 Correct 501 ms 149996 KB Output is correct
3 Correct 396 ms 124892 KB Output is correct
4 Correct 67 ms 85580 KB Output is correct
5 Correct 623 ms 150064 KB Output is correct
6 Correct 499 ms 125016 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 85708 KB Output is correct
2 Correct 498 ms 142116 KB Output is correct
3 Correct 490 ms 142276 KB Output is correct
4 Correct 640 ms 177308 KB Output is correct
5 Correct 61 ms 85664 KB Output is correct
6 Correct 513 ms 149968 KB Output is correct
7 Correct 397 ms 124884 KB Output is correct
8 Correct 663 ms 126592 KB Output is correct
9 Correct 598 ms 125740 KB Output is correct
10 Correct 1235 ms 151392 KB Output is correct
11 Correct 1299 ms 150696 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 61 ms 85708 KB Output is correct
2 Correct 498 ms 142116 KB Output is correct
3 Correct 490 ms 142276 KB Output is correct
4 Correct 640 ms 177308 KB Output is correct
5 Correct 61 ms 85664 KB Output is correct
6 Correct 513 ms 149968 KB Output is correct
7 Correct 397 ms 124884 KB Output is correct
8 Correct 663 ms 126592 KB Output is correct
9 Correct 598 ms 125740 KB Output is correct
10 Correct 1235 ms 151392 KB Output is correct
11 Correct 1299 ms 150696 KB Output is correct
12 Correct 61 ms 85672 KB Output is correct
13 Correct 768 ms 142132 KB Output is correct
14 Correct 1027 ms 175472 KB Output is correct
15 Correct 1004 ms 141892 KB Output is correct
16 Correct 980 ms 142008 KB Output is correct
17 Correct 72 ms 85732 KB Output is correct
18 Correct 628 ms 149996 KB Output is correct
19 Correct 501 ms 124864 KB Output is correct
20 Correct 839 ms 125620 KB Output is correct
21 Correct 821 ms 126028 KB Output is correct
22 Correct 1919 ms 150420 KB Output is correct
23 Correct 2023 ms 170604 KB Output is correct
24 Correct 1497 ms 170208 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 85476 KB Output is correct
2 Correct 78 ms 86764 KB Output is correct
3 Correct 70 ms 86452 KB Output is correct
4 Correct 97 ms 87224 KB Output is correct
5 Correct 89 ms 87256 KB Output is correct
6 Correct 71 ms 86384 KB Output is correct
7 Correct 59 ms 85456 KB Output is correct
8 Correct 240 ms 109792 KB Output is correct
9 Correct 233 ms 109616 KB Output is correct
10 Correct 61 ms 85556 KB Output is correct
11 Correct 505 ms 141964 KB Output is correct
12 Correct 488 ms 141900 KB Output is correct
13 Correct 656 ms 176992 KB Output is correct
14 Correct 62 ms 85452 KB Output is correct
15 Correct 519 ms 149860 KB Output is correct
16 Correct 393 ms 124708 KB Output is correct
17 Correct 609 ms 126612 KB Output is correct
18 Correct 585 ms 125660 KB Output is correct
19 Correct 1199 ms 151188 KB Output is correct
20 Correct 1293 ms 150688 KB Output is correct
21 Correct 258 ms 110508 KB Output is correct
22 Correct 258 ms 109872 KB Output is correct
23 Correct 354 ms 116164 KB Output is correct
24 Correct 346 ms 117540 KB Output is correct
25 Correct 775 ms 130472 KB Output is correct
26 Correct 500 ms 120112 KB Output is correct
27 Correct 471 ms 119184 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 85476 KB Output is correct
2 Correct 78 ms 86764 KB Output is correct
3 Correct 70 ms 86452 KB Output is correct
4 Correct 97 ms 87224 KB Output is correct
5 Correct 89 ms 87256 KB Output is correct
6 Correct 71 ms 86384 KB Output is correct
7 Correct 59 ms 85456 KB Output is correct
8 Correct 240 ms 109792 KB Output is correct
9 Correct 233 ms 109616 KB Output is correct
10 Correct 61 ms 85556 KB Output is correct
11 Correct 505 ms 141964 KB Output is correct
12 Correct 488 ms 141900 KB Output is correct
13 Correct 656 ms 176992 KB Output is correct
14 Correct 62 ms 85452 KB Output is correct
15 Correct 519 ms 149860 KB Output is correct
16 Correct 393 ms 124708 KB Output is correct
17 Correct 609 ms 126612 KB Output is correct
18 Correct 585 ms 125660 KB Output is correct
19 Correct 1199 ms 151188 KB Output is correct
20 Correct 1293 ms 150688 KB Output is correct
21 Correct 258 ms 110508 KB Output is correct
22 Correct 258 ms 109872 KB Output is correct
23 Correct 354 ms 116164 KB Output is correct
24 Correct 346 ms 117540 KB Output is correct
25 Correct 775 ms 130472 KB Output is correct
26 Correct 500 ms 120112 KB Output is correct
27 Correct 471 ms 119184 KB Output is correct
28 Correct 62 ms 85484 KB Output is correct
29 Correct 118 ms 86788 KB Output is correct
30 Correct 94 ms 86524 KB Output is correct
31 Correct 155 ms 87128 KB Output is correct
32 Correct 136 ms 87196 KB Output is correct
33 Correct 80 ms 86476 KB Output is correct
34 Correct 64 ms 85452 KB Output is correct
35 Correct 242 ms 109684 KB Output is correct
36 Correct 193 ms 111548 KB Output is correct
37 Correct 203 ms 111680 KB Output is correct
38 Correct 64 ms 86228 KB Output is correct
39 Correct 751 ms 144828 KB Output is correct
40 Correct 1025 ms 178256 KB Output is correct
41 Correct 1020 ms 144436 KB Output is correct
42 Correct 976 ms 144588 KB Output is correct
43 Correct 64 ms 86264 KB Output is correct
44 Correct 610 ms 152744 KB Output is correct
45 Correct 517 ms 127516 KB Output is correct
46 Correct 770 ms 128332 KB Output is correct
47 Correct 755 ms 128752 KB Output is correct
48 Correct 2020 ms 152916 KB Output is correct
49 Correct 2062 ms 173352 KB Output is correct
50 Correct 1494 ms 169992 KB Output is correct
51 Correct 275 ms 114376 KB Output is correct
52 Correct 230 ms 113372 KB Output is correct
53 Correct 201 ms 113076 KB Output is correct
54 Correct 209 ms 113660 KB Output is correct
55 Correct 232 ms 111488 KB Output is correct
56 Correct 394 ms 119196 KB Output is correct
57 Correct 785 ms 134032 KB Output is correct
58 Correct 821 ms 123808 KB Output is correct
59 Correct 523 ms 123240 KB Output is correct