提出 #54140282

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for(ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

#define TT template<typename T>
TT using vec = vector<T>;
TT bool chmin(T &x, T y) { return x > y ? (x = y, true) : false; }
TT bool chmax(T &x, T y) { return x < y ? (x = y, true) : false; }

struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

struct dsu {
    using vi = vector<int>;   
    using vvi = vec<vi>;
    struct dat {
        int u, v, pv, su, eu, vu;
        dat(){}
        dat(int a, int b, int c, int d, int e) : u(a), v(b), pv(c), su(d), eu(e) {}
    };

    vi par, sz, es;
    stack<dat> his;
    int cc;
   
    public:

    dsu(int n) {
        par = vi(n);
        sz = vi(n, 1);
        es = vi(n, 0);
        cc = n;
        iota(all(par), 0);
    }
  
    int leader(int u) {
        while(par[u] != u) {
            u = par[u];
        }
        return u;
    }
    
    bool same(int a, int b) {
        return leader(a) == leader(b);
    }
    
    bool merge(int a, int b) {
        a = leader(a), b = leader(b);
        if(sz[a] < sz[b]) swap(a, b);
        his.push(dat(a, b, par[b], sz[a], es[a]));

        if(a == b) {
            es[a]++;
            return false;
        }
        else {
            cc--;
            par[b] = a;
            sz[a] += sz[b];
            es[a] += es[b] + 1;
            return true;
        }
    }

    int size(int u) {//uが含まれる連結成分のサイズを返す
        return sz[leader(u)];
    }

    int edgecnt(int u) {
        return es[leader(u)];
    }

    int component_count() {
        return cc;
    }

    bool undo() {
        if(his.empty()) return false;
        dat pre = his.top();
        his.pop();
        par[pre.v] = pre.pv;
        sz[pre.u] = pre.su;
        es[pre.u] = pre.eu;
        return true;
    }

    vvi groups() {
        int n = par.size();
        vvi ms(n);
        rep(v, 0, n) {
            ms[leader(v)].push_back(v);
        }

        vvi res;
        rep(i, 0, n) if(ms[i].size() > 0) {
            res.push_back(ms[i]);
        }

        return res;
    }
};


template<class dsu, class S, class qif>
struct offline_connectivity {
	using pii = pair<int, int>;
	using edge = array<int, 4>;
	using que = pair<int, qif>;
	int n, t, sz, qi;
	dsu uf;
	vec<vec<pii>> dat;
	vec<set<pii>> es;
	vec<edge> lrs;
	vec<que> qs;
	vec<S> res;

	offline_connectivity(int N) : n(N), es(N), qi(0), t(0), sz(1), uf(N) { }

	void build() {
		rep(u, 0, n) {
			for(auto [v, l] : es[u]) {
				lrs.push_back(edge{l, t, u, v});
			}
		}
        t += 1;

		while(sz < t) sz <<= 1;
		dat.resize(2 * sz);

		for(auto [l, r, u, v] : lrs) {
			l += sz;
			r += sz;
			while(l < r) {
				if(l & 1) dat[l++].emplace_back(u, v);
				if(r & 1) dat[--r].emplace_back(u, v);
				l >>= 1, r >>= 1;
			}
		}
	}

	TT void dfs(T f, int v) {
		for(auto [a, b] : dat[v]) uf.merge(a, b);
		if(v >= sz) {
			if(qi < qs.size() && qs[qi].first == v - sz) res.push_back(f(uf, qs[qi++].second));
		}
		else {
			dfs(f, v * 2);
			dfs(f, v * 2 + 1);
		}
		rep(i, 0, dat[v].size()) uf.undo();
	}
    

	TT vec<S> run(T f) {
		dfs(f, 1);
		return res;
	}

	void link(int u, int v) {
		if(u > v) swap(u, v);
		es[u].insert(pii(v, t));
	}

	void cut(int u, int v) {
		if(u > v) swap(u, v);
		auto it = es[u].lower_bound(pii(v+1, -1));
		if(it == es[u].begin()) return;
		
		it--;
		auto [tar, l] = *it;
		if(tar != v) return;
		es[u].erase(it);
		lrs.push_back(edge{l, t, u, v});
		
	}

	void query(qif q) {
		qs.push_back(que(t++, q));
	}
};


using pll = pair<ll, ll>;
#define pb push_back

ll f(dsu &uf, ll v) {
	return uf.size(v);
}



int main() {
	ll Q, K;
	cin >> Q >> K;
	offline_connectivity<dsu, ll, ll> uf(Q+10);
	vec<pll> qs(Q);
	vec<ll> cmp;
	set<ll> aru;

	rep(qi, 0, Q) {
		ll t, x;
		cin >> t >> x;
		qs[qi] = pll(t, x);
		cmp.push_back(x);
	}

	sort(all(cmp));
    cmp.erase(unique(all(cmp)), cmp.end());

	auto get = [&](ll x) {
		return lower_bound(all(cmp), x) - cmp.begin();
	};

	vec<vec<int>> es(Q+10);

	
	rep(qi, 0, Q) {
		auto [t, x] = qs[qi];
		ll id = get(x);
		auto itr = aru.lower_bound(x);

		if(t == 1) {
			if(itr == aru.end() || *itr != x) {
				//挿入
				ll pre = -1;
				ll nex = -1;

				if(itr != aru.begin()) {
					itr--;
					pre = *itr;
					itr++;
				}

				if(itr != aru.end()) {
					nex = *itr;
				}

				ll pid = -1, nid = -1;
				if(pre != -1) pid = get(pre);
				if(nex != -1) nid = get(nex);

				if(pid != -1&&abs(pre - x) <= K)uf.link(pid, id);
				if(nid != -1&& abs(nex - x) <= K)uf.link(id, nid);
				if(pid != -1&& abs(pre - x) <= K)es[pid].pb(id);
				if(pid != -1&& abs(pre - x) <= K)es[id].pb(pid);
				if(nid != -1&& abs(nex - x) <= K)es[id].pb(nid);
				if(nid != -1&& abs(nex - x) <= K)es[nid].pb(id);
				aru.insert(x);
			}
			else {
				//削除

				ll pre = -1;
				ll nex = -1;

				if(itr != aru.begin()) {
					itr--;
					pre = *itr;
					itr++;
				}

				itr++;
				if(itr != aru.end()) {
					nex = *itr;
				}
				itr--;

				if(pre != -1 && nex != -1) {
					ll pid = get(pre);
					ll nid = get(nex);
					if(abs(pre - nex) <= K) {
					  uf.link(pid, nid);
					  es[pid].pb(nid);
					  es[nid].pb(pid);
					}
				}

				//あとは辺の削除
				for(int to : es[id]) {
					uf.cut(id, to);
				}

				es[id] = vec<int>();
				aru.erase(x);
			}
		}
		else {
			uf.query(id);
		}
	}

	uf.build();
	auto ans = uf.run(f);
	for(auto v : ans) cout << v << '\n';



	
	
	
}

提出情報

提出日時
問題 F - Distance Component Size Query
ユーザ Astral__
言語 C++ 20 (gcc 12.2)
得点 525
コード長 6009 Byte
結果 AC
実行時間 228 ms
メモリ 60096 KiB

コンパイルエラー

Main.cpp: In instantiation of ‘offline_connectivity<dsu, S, qif>::offline_connectivity(int) [with dsu = dsu; S = long long int; qif = long long int]’:
Main.cpp:204:43:   required from here
Main.cpp:121:23: warning: ‘offline_connectivity<dsu, long long int, long long int>::es’ will be initialized after [-Wreorder]
  121 |         vec<set<pii>> es;
      |                       ^~
Main.cpp:118:23: warning:   ‘int offline_connectivity<dsu, long long int, long long int>::qi’ [-Wreorder]
  118 |         int n, t, sz, qi;
      |                       ^~
Main.cpp:126:9: warning:   when initialized here [-Wreorder]
  126 |         offline_connectivity(int N) : n(N), es(N), qi(0), t(0), sz(1), uf(N) { }
      |         ^~~~~~~~~~~~~~~~~~~~
Main.cpp:118:23: warning: ‘offline_connectivity<dsu, long long int, long long int>::qi’ will be initialized after [-Wreorder]
  118 |         int n, t, sz, qi;
      |                       ^~
Main.cpp:118:16: warning:   ‘int offline_connectivity<dsu, long long int, long long int>::t’ [-Wreorder]
  118 |         int n, t, sz, qi;
      |                ^
Main.cpp:126:9: warning:   when initialized here [-Wreorder]
  126 |         offline_connectivity(int N) : n(N), es(N), qi(0), t(0), sz(1), uf(N) { }
      |         ^~~~~~~~~~~~~~~~~~~~
Main.cpp: In instantiation of ‘void offline_connectivity<dsu, S, qif>::build() [with dsu = dsu; S = long long int; qif = long long int]’:
Main.cpp:301:10:   required from here
Main.cpp:131:58: warning: narrowing conversion of ‘u’ from ‘ll’ {aka ‘long long int’} to ‘int’ [-Wnarrowing]
  131 |                                 lrs.push_back(edge{l, t, u, v});
      |                                                          ^
Main.cpp: In instantiation of ‘void offline_connectivity<dsu, S, qif>::dfs(T, int) [with T = long long int (*)(dsu&, long long int); dsu = dsu; S = long long int; qif = long long int]’:
Main.cpp:164:6:   required from ‘vec<S> offline_connectivity<dsu, S, qif>::run(T) [with T = long long int (*)(dsu&, long long int); dsu = dsu; S = long long int; qif = long long int; vec<S> = std::vector<long long int, std::allocator<long long int> >]’
Main.cpp:302:19:   required from here
Main.cpp:153:31: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, long long int>, std::allocator<std::pair<int, long long int> > >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  153 |                         if(qi < qs.size() && qs[qi].first == v - sz) res.push_back(f(uf, qs[qi++].second));
      |                            ~~~^~~~~~~~~~~

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 525 / 525
結果
AC × 3
AC × 41
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, random_36.txt, random_37.txt, random_38.txt, sample_01.txt, sample_02.txt, sample_03.txt
ケース名 結果 実行時間 メモリ
random_01.txt AC 68 ms 26560 KiB
random_02.txt AC 62 ms 33620 KiB
random_03.txt AC 64 ms 42816 KiB
random_04.txt AC 85 ms 26532 KiB
random_05.txt AC 80 ms 33728 KiB
random_06.txt AC 74 ms 42940 KiB
random_07.txt AC 105 ms 26944 KiB
random_08.txt AC 96 ms 33704 KiB
random_09.txt AC 86 ms 42896 KiB
random_10.txt AC 78 ms 29320 KiB
random_11.txt AC 80 ms 37236 KiB
random_12.txt AC 69 ms 44248 KiB
random_13.txt AC 111 ms 31428 KiB
random_14.txt AC 106 ms 39300 KiB
random_15.txt AC 82 ms 44564 KiB
random_16.txt AC 144 ms 34604 KiB
random_17.txt AC 130 ms 41136 KiB
random_18.txt AC 95 ms 45028 KiB
random_19.txt AC 101 ms 32376 KiB
random_20.txt AC 103 ms 41648 KiB
random_21.txt AC 78 ms 45828 KiB
random_22.txt AC 156 ms 39788 KiB
random_23.txt AC 151 ms 47536 KiB
random_24.txt AC 97 ms 47080 KiB
random_25.txt AC 218 ms 49668 KiB
random_26.txt AC 206 ms 52952 KiB
random_27.txt AC 122 ms 48548 KiB
random_28.txt AC 158 ms 39980 KiB
random_29.txt AC 154 ms 47016 KiB
random_30.txt AC 98 ms 47168 KiB
random_31.txt AC 218 ms 49520 KiB
random_32.txt AC 203 ms 53176 KiB
random_33.txt AC 122 ms 48500 KiB
random_34.txt AC 27 ms 24244 KiB
random_35.txt AC 181 ms 58612 KiB
random_36.txt AC 228 ms 59364 KiB
random_37.txt AC 227 ms 60096 KiB
random_38.txt AC 226 ms 59996 KiB
sample_01.txt AC 1 ms 3388 KiB
sample_02.txt AC 1 ms 3440 KiB
sample_03.txt AC 1 ms 3596 KiB