제출 #586923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586923		pavement	Inside information (BOI21_servers)	C++17	100 / 100	2062 ms	178256 KiB

servers

#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';
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5