답안 #813988

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
813988 2023-08-08T04:53:07 Z 박상훈(#10120) Posters on the wall (CPSPC17_posters) C++17
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, k;
vector<int> adj[100100], H[100100];

struct Seg{
	pair<int, int> tree[400400], lazy[400400];
	void init(int i, int l, int r){
		tree[i] = lazy[i] = {-1, -1};
		if (l==r) return;

		int m = (l+r)>>1;
		init(i<<1, l, m); init(i<<1|1, m+1, r);
	}

	void propagate(int i, int l, int r){
		if (lazy[i].second==-1) return;
		tree[i] = {r+lazy[i].first, lazy[i].second};

		if (l!=r){
			lazy[i<<1] = lazy[i];
			lazy[i<<1|1] = lazy[i];
		}

		lazy[i] = {-1, -1};
	}

	void update(int i, int l, int r, int s, int e, int c, int x){
		propagate(i, l, r);
		if (r<s || e<l) return;
		if (s<=l && r<=e){
			lazy[i] = {c, x};
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		update(i<<1, l, m, s, e, c, x); update(i<<1|1, m+1, r, s, e, c, x);
		tree[i] = max(tree[i<<1], tree[i<<1|1]);
	}

	pair<int, int> query(int i, int l, int r, int s, int e){
		propagate(i, l, r);
		if (r<s || e<l) return {-1, -1};
		if (s<=l && r<=e) return tree[i];

		int m = (l+r)>>1;
		return max(query(i<<1, l, m, s, e), query(i<<1|1, m+1, r, s, e));
	}

	void clear(int i, int l, int r, int p){
		tree[i] = lazy[i] = {-1, -1};
		if (l==r) return;
		if (r<p || p<l) return;

		int m = (l+r)>>1;
		clear(i<<1, l, m, p); clear(i<<1|1, m+1, r, p);
	}
};

struct DSU{
	int path[100100], root[100100];
	void init(const vector<int> &a){
		for (int i=0;i<(int)a.size();i++){
			path[i] = i;
			root[i] = a[i];
		}
	}

	int find(int s){
		if (path[s]==s) return s;
		return path[s] = find(path[s]);
	}

	void merge(int l, int r, int v){
		l = path[l], r = path[r];
		assert(l!=r);
		path[r] = l;
		root[l] = v;
	}

	int calc(int s){return root[find(s)];}
}dsu;

namespace HLD{

Seg tree;
vector<int> G[100100], buf;

int par[100100], dep[100100], sz[100100], top[100100], in[100100], INV[100100], cnt;

void dfs0(int s, int pa){
	par[s] = pa;
	dep[s] = dep[pa] + 1;
	sz[s] = 1;

	for (auto &v:adj[s]) if (v!=pa){
		G[s].push_back(v);
		// printf("%d -> %d\n", s, v);
		dfs0(v, s);

		sz[s] += sz[v];
	}
}

void dfs1(int s){
	// printf("dfs %d\n", s);
	if (!G[s].empty()) swap(G[s][0], *max_element(G[s].begin(), G[s].end(), [&](int i, int j){return sz[i] < sz[j];}));
	in[s] = ++cnt;
	INV[cnt] = s;

	for (auto &v:G[s]){
		if (v==G[s][0]) top[v] = top[s];
		else top[v] = v;

		dfs1(v);
	}
}

void init(){
	for (int i=1;i<=n;i++) G[i].clear();
	top[1] = 1;
	cnt = 0;
	
	dfs0(1, 0);
	dfs1(1);
	
	tree.init(1, 1, n);
}

pair<int, int> query(int s, int e){
	assert(dep[s] <= dep[e]);

	pair<int, int> ret = {-1, -1};

	while(top[s]!=top[e]){
		ret = max(ret, tree.query(1, 1, n, in[top[e]], in[e]));
		e = par[top[e]];
		assert(dep[s] <= dep[e]);
	}

	ret = max(ret, tree.query(1, 1, n, in[s], in[e]));
	return ret;
}

void update(int s, int e, int x){
	assert(dep[s] <= dep[e]);

	while(top[s]!=top[e]){
		tree.update(1, 1, n, in[top[e]], in[e], -in[e]+dep[e], x);
		e = par[top[e]];
		assert(dep[s] <= dep[e]);
	}

	tree.update(1, 1, n, in[s], in[e], -in[e]+dep[e], x);
}

int LCA(int x, int y){
	while(top[x]!=top[y]){
		if (dep[top[x]] > dep[top[y]]) swap(x, y);
		y = par[top[y]];
		// printf("ok %d %d\n", x, y);
	}

	if (dep[x] > dep[y]) swap(x, y);
	return x;
}

int calc(int x, int y){
	x = INV[x], y = INV[y];
	return dep[LCA(x, y)];
}

void push(int x){buf.push_back(x);}

void compress(){
	sort(buf.begin(), buf.end(), [&](int i, int j){return in[i] < in[j];});
	buf.erase(unique(buf.begin(), buf.end()), buf.end());
	for (auto &x:buf) H[x].clear();

	vector<array<int, 4>> E;
	for (int i=0;i<(int)buf.size()-1;i++){
		int lca = LCA(buf[i], buf[i+1]);
		E.push_back({dep[lca], lca, i, i+1});
		H[lca].clear();
	} 
	sort(E.begin(), E.end(), greater<array<int, 4>>());
	
	dsu.init(buf);
	for (auto &[_, v, l, r]:E){
		int x = dsu.calc(l), y = dsu.calc(r);

		if (dep[v] < dep[x]) H[v].push_back(x);
		if (dep[v] < dep[y]) H[v].push_back(y);

		dsu.merge(l, r, v);
		buf.push_back(v);
	}
}

} // namespace HLD

struct DS{
	multimap<array<int, 3>, int> st;
	multiset<array<int, 3>> stAns;

	void clear(){
		st.clear();
		stAns.clear();
	}

	void insert(int ord, int ord2, int x){
		auto iter = st.find({ord2, ord, x});
		if (iter!=st.end()){
			auto piter = (iter!=st.begin())?prev(iter):iter;
			auto niter = next(iter);
			if (iter!=st.begin()) 
				stAns.erase({piter->second, (piter->first)[2], (iter->first)[2]});
			if (niter!=st.end()) 
				stAns.erase({iter->second, (iter->first)[2], (niter->first)[2]});
			if (iter!=st.begin() && niter!=st.end()) 
				stAns.insert({piter->second = HLD::calc((piter->first)[0], (niter->first)[0]), (piter->first)[2], (niter->first)[2]});

			st.erase(iter);
		}

		else{
			iter = st.insert({array<int, 3>{ord, ord2, x}, 0});
			auto piter = (iter!=st.begin())?prev(iter):iter;
			auto niter = next(iter);
			if (iter!=st.begin() && niter!=st.end())
				stAns.erase({piter->second, (piter->first)[2], (niter->first)[2]});
			if (iter!=st.begin()) 
				stAns.insert({piter->second = HLD::calc((piter->first)[0], (iter->first)[0]), (piter->first)[2], (iter->first)[2]});
			if (niter!=st.end()) 
				stAns.insert({iter->second = HLD::calc((iter->first)[0], (niter->first)[0]), (iter->first)[2], (niter->first)[2]});
		}
	}

	array<int, 3> query(){
		if (stAns.empty()) return {-1, -1, -1};
		return *stAns.rbegin();
	}
}D[100100];

vector<int> solve5(vector<array<int, 3>> &Q){
	sort(Q.begin(), Q.end(), [&](array<int, 3> i, array<int, 3> j){return HLD::dep[i[0]] < HLD::dep[j[0]];});

	vector<int> ret(3);
	ret[0] = 0, ret[1] = 0, ret[2] = 1;

	for (auto &[s, e, x]:Q){
		auto [d, y] = HLD::query(s, e);
		HLD::update(s, e, x);
		if (d <= HLD::dep[s]) continue;

		if (ret[0] < d - HLD::dep[s]){
			ret[0] = d - HLD::dep[s];
			ret[1] = x;
			ret[2] = y;
		}
	}

	return ret;
}

vector<int> ret6;

void merge(DS &D, DS &E){
	if (D.st.size() < E.st.size()) swap(D, E);
	for (auto &[A, B]:E.st) D.insert(A[0], A[1], A[2]);
}

void dfs2(int s, int root){
	for (auto &v:H[s]){
		dfs2(v, root);
		merge(D[s], D[v]);
	}

	if (s!=root){
		auto [val, x, y] = D[s].query();
		if (val==-1) val = -1e9;
		val += HLD::dep[s] - HLD::dep[root] * 2;

		if (val > ret6[0]){
			ret6[0] = val, ret6[1] = x, ret6[2] = y;
		}

	}
}

vector<int> solve6(int root, vector<array<int, 3>> &Q){
	ret6.clear();
	ret6.resize(3);
	ret6[0] = 0, ret6[1] = 0, ret6[2] = 1;

	HLD::buf.clear();
	HLD::push(root);
	for (auto &[s, e, x]:Q){
		HLD::push(s);
		HLD::push(e);
	}

	HLD::compress();
	for (auto &x:HLD::buf) D[x].clear();

	for (auto &[s, e, x]:Q){
		D[s].insert(HLD::in[e], HLD::in[s], x);
		D[e].insert(HLD::in[s], HLD::in[e], x);
	}

	dfs2(root, root);
	return ret6;
}

vector<array<int, 3>> buf2[100100];
std::vector<int> post(std::vector<int> U, std::vector<int> V, std::vector<int> S, std::vector<int> E) {
	n = U.size() + 1;
	k = S.size();

	for (int i=0;i<n-1;i++){
		U[i]++, V[i]++;
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}

	HLD::init();

	vector<array<int, 3>> buf1;

	for (int i=0;i<k;i++){
		S[i]++, E[i]++;
		int lca = HLD::LCA(S[i], E[i]);
		buf1.push_back({lca, S[i], i});
		buf1.push_back({lca, E[i], i});

		// printf("ok lca = %d\n", lca);
		buf2[lca].push_back({S[i], E[i], i});
	}

	auto ans1 = solve5(buf1);
	// return ans1; // subtask 5

	HLD::tree.init(1, 1, n);

	for (int i=1;i<=n;i++){
		auto ans2 = solve6(i, buf2[i]);
		if (ans2[0] > ans1[0]) swap(ans1, ans2);
	}

	return ans1;
}

Compilation message

/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/crt1.o: in function `_start':
(.text+0x24): undefined reference to `main'
collect2: error: ld returned 1 exit status