Submission #91879

#	Time	Username	Problem	Language	Result	Execution time	Memory
91879		tmwilliamlin168	Min-max tree (BOI18_minmaxtree)	C++14	22 / 100	304 ms	57868 KiB

minmaxtree

#include <bits/stdc++.h>
using namespace std;

const int mxN=7e4;
int n, ui, vi, d[mxN], anc[mxN][17], c1[mxN][17], c2[mxN][17], k, wi;
vector<int> adj[mxN];
char qt;
unordered_map<int, int> mp;

void dfs(int u=n-1, int p=-1) {
	anc[u][0]=p;
	for(int i=1; i<17; ++i)
		anc[u][i]=anc[u][i-1]==-1?-1:anc[anc[u][i-1]][i-1];
	d[u]=p==-1?0:d[p]+1;
	for(int v : adj[u])
		if(v!=p)
			dfs(v, u);
}

#define y(x) (2*(x))
#define n(x) (2*(x)+1)
struct twosat {
	static const int mxN=3*(::mxN-1);
	int n, c[2*mxN];
	vector<int> a1[2*mxN], a2[2*mxN], st;
	bool vis[2*mxN], ans[2*mxN];
	void imp(int u, int v) {
		a1[u].push_back(v);
		a1[v^1].push_back(u^1);
	}
	void dfs1(int u) {
		vis[u]=1;
		for(int v : a1[u])
			if(!vis[v])
				dfs1(v);
		st.push_back(u);
	}
	void dfs2(int u, int cu) {
		vis[u]=0;
		c[u]=cu;
		for(int v : a2[u])
			if(vis[v])
				dfs2(v, cu);
	}
	bool ac() {
		for(int i=0; i<2*n; ++i)
			if(!vis[i])
				dfs1(i);
		for(int i=0; i<2*n; ++i)
			for(int j : a1[i])
				a2[j].push_back(i);
		for(int i=n-1; i>=0; --i)
			if(vis[st[i]])
				dfs2(st[i], i);
		for(int i=0; i<2*n; i+=2) {
			if(c[i]==c[i^1])
				return 0;
			ans[i]=c[i]<c[i^1];
		}
		return 1;
	}
} ts;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for(int i=0; i<n-1; ++i) {
		cin >> ui >> vi, --ui, --vi;
		adj[ui].push_back(vi);
		adj[vi].push_back(ui);
	}
	dfs();
	memset(c2, 0x96, sizeof(c2));
	cin >> k;
	while(k--) {
		cin >> qt >> ui >> vi >> wi, --ui, --vi;
		int (*c)[17];
		if(qt=='M') {
			wi=-wi;
			c=c2;
		} else
			c=c1;
		if(d[ui]<d[vi])
			swap(ui, vi);
		auto ue=[&](int &u, int i) {
			c[u][i]=max(wi, c[u][i]);
			u=anc[u][i];
		};
		for(int i=16; i>=0; --i)
			if(d[ui]-(1<<i)>=d[vi])
				ue(ui, i);
		if(ui!=vi) {
			for(int i=16; i>=0; --i) {
				if(anc[ui][i]!=anc[vi][i]) {
					ue(ui, i);
					ue(vi, i);
				}
			}
			ue(ui, 0);
			ue(vi, 0);
		}
	}
	for(int i=16; i; --i) {
		for(int j=0; j<n; ++j) {
			c1[j][i-1]=max(c1[j][i], c1[j][i-1]);
			c2[j][i-1]=max(c2[j][i], c2[j][i-1]);
			if(anc[j][i-1]!=-1) {
				c1[anc[j][i-1]][i-1]=max(c1[j][i], c1[anc[j][i-1]][i-1]);
				c2[anc[j][i-1]][i-1]=max(c2[j][i], c2[anc[j][i-1]][i-1]);
			}
		}
	}
	for(int i=0; i<n-1; ++i) {
		ts.imp(y(i), y(i+n-1));
		if(mp.find(c1[i][0])!=mp.end())
			ts.imp(y(mp[c1[i][0]]), y(i+n-1));
		mp[c1[i][0]]=i+n-1;
		c2[i][0]=-c2[i][0];
		ts.imp(n(i), y(i+2*(n-1)));
		if(mp.find(c2[i][0])!=mp.end())
			ts.imp(y(mp[c2[i][0]]), y(i+2*(n-1)));
		mp[c2[i][0]]=i+2*(n-1);
	}
	for(auto it=mp.begin(); it!=mp.end(); ++it)
		if(1<=it->first&&it->first<=1e9)
			ts.imp(n(it->second), y(it->second));
	ts.ac();
	for(int i=0; i<n-1; ++i)
		cout << i+1 << " " << anc[i][0]+1 << " " << (ts.ans[y(i)]?c1[i][0]:c2[i][0]) << "\n";
}

• Subtask 1: 0 / 7
• Subtask 2: 22 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42