Submission #592939

#	Time	Username	Problem	Language	Result	Execution time	Memory
592939		Bobaa	Min-max tree (BOI18_minmaxtree)	C++17	100 / 100	148 ms	22788 KiB

minmaxtree

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

const int inf = 1e9 + 7; 
const int maxn = 7e4 + 5; 

int n; 

struct query {
	int x, y, z; 
	char scan() {
		static char in[10]; 
		scanf("%s %d %d %d", in, &x, &y, &z); 
		return *in; 
	}
};

vector<int> edge[maxn]; 
vector<query> qs[256]; 
int par[maxn][17]; 
int nxt[maxn]; 
int dep[maxn]; 

void dfs(int x, int p) {
	par[x][0] = p; 
	dep[x] = dep[p] + 1; 
	for (int i = 1; i < 17; i++) par[x][i] = par[par[x][i - 1]][i - 1]; 
	for (int i : edge[x]) {
		if (i == p) continue; 
		dfs(i, x); 
	}
}

int lca(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i = 17; i--; ) if ((dep[x] - dep[y]) >> i) x = par[x][i]; 
	if (x == y) return x; 
	for (int i = 17; i--; ) if (par[x][i] != par[y][i]) {
		x = par[x][i]; 
		y = par[y][i]; 
	}
	return par[x][0]; 
}

int mn[maxn]; 
int mx[maxn]; 

int paint(int c[], int s, int e, int x) {
	if (dep[s] <= dep[e]) return s; 
	if (c[s]) return nxt[s] = paint(c, nxt[s], e, x); 
	c[s] = x; 
	return nxt[s] = paint(c, par[s][0], e, x); 
}

int find(vector<int> &v, int x) {
	return lower_bound(v.begin(), v.end(), x) - v.begin(); 
}

struct matching {
	vector<int> edge[maxn]; 
	int rev[maxn]; 
	int vis[maxn]; 
	int lv[maxn]; 
	int n; 
	
	void bfs() {
		queue<int> q; 
		for (int i = 2; i <= n; i++) {
			if (vis[i]) lv[i] = inf; 
			else {
				lv[i] = 0; 
				q.push(i); 
			}
		}
		while (!q.empty()) {
			int x = q.front(); 
			q.pop(); 
			for (int i : edge[x]) if (rev[i]) {
				if (lv[rev[i]] < inf) continue; 
				lv[rev[i]] = lv[x] + 1; 
				q.push(rev[i]); 
			}
		}
	}
	
	int dfs(int x) {
		for (int i : edge[x]) if (rev[i] == 0 || lv[rev[i]] == lv[x] + 1 && dfs(rev[i])) {
			vis[x] = 1; 
			rev[i] = x; 
			return 1; 
		}
		return 0; 
	}
	
	int process(int N) {
		n = N; 
		int ret = 0; 
		while (1) {
			bfs(); 
			int res = 0; 
			for (int i = 2; i <= n; i++) {
				if (vis[i]) continue; 
				res += dfs(i); 
			}
			if (res == 0) break; 
			ret += res; 
		}
		return ret; 
	}
} mt; 

int main() {
	scanf("%d", &n); 
	for (int i = 1, a, b; i < n; i++) {
		scanf("%d %d", &a, &b); 
		edge[a].push_back(b); 
		edge[b].push_back(a); 
	}
	dfs(1, 0); 
	int k; 
	scanf("%d", &k); 
	vector<int> cp; 
	for (int i = 0; i < k; i++) {
		query q; 
		char c = q.scan(); 
		qs[c].push_back(q); 
		cp.push_back(q.z); 
	}
	cp.push_back(0); 
	sort(cp.begin(), cp.end()); 
	cp.erase(unique(cp.begin(), cp.end()), cp.end()); 
	sort(qs['m'].begin(), qs['m'].end(), [&](const query &x, const query &y) {
		return x.z > y.z; 
	}); 
	sort(qs['M'].begin(), qs['M'].end(), [&](const query &x, const query &y) {
		return x.z < y.z; 
	}); 
	for (query i : qs['m']) {
		int p = lca(i.x, i.y); 
		paint(mn, i.x, p, i.z); 
		paint(mn, i.y, p, i.z); 
	}
	for (query i : qs['M']) {
		int p = lca(i.x, i.y); 
		paint(mx, i.x, p, i.z); 
		paint(mx, i.y, p, i.z);
	}
	for (int i = 2; i <= n; i++) {
		if (mn[i]) mt.edge[i].push_back(find(cp, mn[i])); 
		if (mn[i] == mx[i]) continue; 
		if (mx[i]) mt.edge[i].push_back(find(cp, mx[i])); 
	}
	mt.process(n); 
	for (int i = 1; i < cp.size(); i++) mn[mt.rev[i]] = cp[i]; 
	for (int i = 2; i <= n; i++) printf("%d %d %d\n", i, par[i][0], mn[i]); 
	return 0; 
}

Compilation message (stderr)

minmaxtree.cpp: In member function 'int matching::dfs(int)':
minmaxtree.cpp:87:68: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   87 |   for (int i : edge[x]) if (rev[i] == 0 || lv[rev[i]] == lv[x] + 1 && dfs(rev[i])) {
      |                                            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:126:6: warning: array subscript has type 'char' [-Wchar-subscripts]
  126 |   qs[c].push_back(q);
      |      ^
minmaxtree.cpp:154:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |  for (int i = 1; i < cp.size(); i++) mn[mt.rev[i]] = cp[i];
      |                  ~~^~~~~~~~~~~
minmaxtree.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
minmaxtree.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~
minmaxtree.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |  scanf("%d", &k);
      |  ~~~~~^~~~~~~~~~
minmaxtree.cpp: In member function 'char query::scan()':
minmaxtree.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%s %d %d %d", in, &x, &y, &z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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