Submission #650880

#	Time	Username	Problem	Language	Result	Execution time	Memory
650880		GusterGoose27	Min-max tree (BOI18_minmaxtree)	C++11	100 / 100	349 ms	56828 KiB

minmaxtree

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 7e4;
const int inf = 2e9;
int n, m;

class edge {
public:
	int dest, rev_id;
	bool full;
	edge(int d, bool f, int r) : dest(d), full(f), rev_id(r) {}
};

class dinic {
public:
	vector<edge> adj[2*MAXN+1]; // start, end, n-1 edges
	int sz, s, t;
	dinic() {}
	dinic(int sz, int s, int t) : sz(sz), s(s), t(t) {}
	int level[2*MAXN+1];
	int ptr[2*MAXN+1];
	void add_edge(int u, int v) {
		adj[u].push_back(edge(v, 0, adj[v].size()));
		adj[v].push_back(edge(u, 1, adj[u].size()-1));
	}
	bool bfs() {
		queue<int> q;
		fill(level, level+sz, -1);
		level[s] = 0;
		q.push(s);
		while (!q.empty() && level[t] == -1) {
			int cur = q.front();
			q.pop();
			for (edge e: adj[cur]) {
				if (e.full || level[e.dest] != -1) continue;
				level[e.dest] = level[cur]+1;
				q.push(e.dest);
			}
		}
		return level[t] != -1;
	}
	void rev(int cur) {
		edge e = adj[cur][ptr[cur]];
		adj[cur][ptr[cur]].full = 1;
		adj[e.dest][e.rev_id].full = 0;
	}
	bool get_flow(int cur) {
		if (cur == t) return 1;
		for (; ptr[cur] < adj[cur].size(); ptr[cur]++) {
			edge e = adj[cur][ptr[cur]];
			if (level[e.dest] != level[cur]+1 || e.full) continue;
			bool is_flow = get_flow(e.dest);
			if (is_flow) {
				rev(cur);
				if (cur != s) {
					ptr[cur]++;
					return 1;
				}
			}
		}
		return 0;
	} 
	void make_match() {
		while (bfs()) {
			fill(ptr, ptr+sz, 0);
			get_flow(s);
		}
	}
};

vector<pii> edges[MAXN];
vector<pii> max_del[MAXN];
vector<pii> min_del[MAXN];
vector<pii> max_add[MAXN];
vector<pii> min_add[MAXN];
set<pii> *max_vals[MAXN];
set<pii> *min_vals[MAXN];
dinic matcher;
int lca[MAXN][17];
int par_edge_val[MAXN];
int depth[MAXN];
int corr_val[MAXN];
pii edge_list[MAXN];
int req[MAXN];
// ifstream cin("tree.in");

int get_lca(int x, int y) {
	if (depth[x] > depth[y]) return get_lca(y, x);
	int def = depth[y]-depth[x];
	int pow = 0;
	while (def > 0) {
		if (def & 1) {
			y = lca[y][pow];
		}
		def >>= 1;
		pow++;
	}
	for (int i = 16; i >= 0; i--) {
		if (lca[x][i] != lca[y][i]) {
			x = lca[x][i];
			y = lca[y][i];
		}
	}
	if (x == y) return x;
	return lca[x][0];
}

void dfs(int cur = 0, int p = 0) {
	lca[cur][0] = p;
	for (pii e: edges[cur]) {
		int nxt = e.first;
		if (nxt == p) continue;
		depth[nxt] = depth[cur]+1;
		par_edge_val[nxt] = e.second;
		dfs(nxt, cur);
	}
}

void make_lca() {
	dfs();
	for (int i = 1; i < 17; i++) {
		for (int j = 0; j < n; j++) lca[j][i] = lca[lca[j][i-1]][i-1];
	}
}

set<pii> *merge(set<pii> *a, set<pii> *b) {
	if (a->size() > b->size()) return merge(b, a);
	for (pii p: (*a)) b->insert(p);
	delete a;
	return b;
}

void make_dinic(int cur = 0, int p = -1) {
	max_vals[cur] = new set<pii>;
	min_vals[cur] = new set<pii>;
	for (pii e: edges[cur]) {
		int nxt = e.first;
		if (nxt == p) continue;
		make_dinic(nxt, cur);
		if (cur > 0) max_vals[cur] = merge(max_vals[cur], max_vals[nxt]);
		if (cur > 0) min_vals[cur] = merge(min_vals[cur], min_vals[nxt]);
	}
	if (cur == 0) return;
	matcher.add_edge(n-1, par_edge_val[cur]);
	for (pii entry: max_add[cur]) max_vals[cur]->insert(entry);
	for (pii entry: max_del[cur]) max_vals[cur]->erase(entry);
	for (pii entry: min_add[cur]) min_vals[cur]->insert(entry);
	for (pii entry: min_del[cur]) min_vals[cur]->erase(entry);
	if (!max_vals[cur]->empty()) matcher.add_edge(par_edge_val[cur], max_vals[cur]->begin()->second+n);
	if (!min_vals[cur]->empty()) {
		matcher.add_edge(par_edge_val[cur], min_vals[cur]->rbegin()->second+n);
		req[par_edge_val[cur]] = min_vals[cur]->rbegin()->first;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n-1; i++) {
		req[i] = 1;
		int x, y; cin >> x >> y;
		edge_list[i] = pii(x, y);
		x--; y--;
		edges[x].push_back(pii(y, i));
		edges[y].push_back(pii(x, i));
	}
	make_lca();
	cin >> m;
	matcher = dinic(n+m+1, n-1, n+m);
	for (int i = 0; i < m; i++) {
		char c;
		int x, y, v;
		cin >> c >> x >> y >> v;
		x--; y--;
		corr_val[i] = v;
		int l = get_lca(x, y);
		if (c == 'M') {
			max_add[x].push_back(pii(v, i));
			max_add[y].push_back(pii(v, i));
			max_del[l].push_back(pii(v, i));
		}
		else {
			min_add[x].push_back(pii(v, i));
			min_add[y].push_back(pii(v, i));
			min_del[l].push_back(pii(v, i));
		}
		matcher.add_edge(n+i, n+m);
	}
	// cerr << "step1" << endl;
	make_dinic();
	matcher.make_match();
	// cerr << "step2" << endl;
	for (int i = 0; i < n-1; i++) {
		cout << edge_list[i].first << " " << edge_list[i].second << " ";
		bool found = 0;
		for (int out = 1; out < matcher.adj[i].size(); out++) {
			if (matcher.adj[i][out].full) {
				cout << corr_val[matcher.adj[i][out].dest-n] << "\n";
				found = 1;
				break;
			}
		}
		if (!found) cout << req[i] << "\n";
	}
	return 0;
}

Compilation message (stderr)

minmaxtree.cpp: In constructor 'edge::edge(int, bool, int)':
minmaxtree.cpp:17:7: warning: 'edge::full' will be initialized after [-Wreorder]
   17 |  bool full;
      |       ^~~~
minmaxtree.cpp:16:12: warning:   'int edge::rev_id' [-Wreorder]
   16 |  int dest, rev_id;
      |            ^~~~~~
minmaxtree.cpp:18:2: warning:   when initialized here [-Wreorder]
   18 |  edge(int d, bool f, int r) : dest(d), full(f), rev_id(r) {}
      |  ^~~~
minmaxtree.cpp: In member function 'bool dinic::get_flow(int)':
minmaxtree.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (; ptr[cur] < adj[cur].size(); ptr[cur]++) {
      |          ~~~~~~~~~^~~~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:203:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |   for (int out = 1; out < matcher.adj[i].size(); out++) {
      |                     ~~~~^~~~~~~~~~~~~~~~~~~~~~~

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