Submission #592937

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
592937	2022-07-09T20:59:46 Z	Bobaa	Min-max tree (BOI18_minmaxtree)	C++17	Compilation error	0 ms	0 KB

minmaxtree

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

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

int n; 

struct qry {
	int x, y, z; 
	char scanf() {
		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

minmaxtree.cpp: In member function 'char qry::scanf()':
minmaxtree.cpp:13:38: error: no matching function for call to 'qry::scanf(const char [12], char [10], int*, int*, int*)'
   13 |   scanf("%s %d %d %d", in, &x, &y, &z);
      |                                      ^
minmaxtree.cpp:11:7: note: candidate: 'char qry::scanf()'
   11 |  char scanf() {
      |       ^~~~~
minmaxtree.cpp:11:7: note:   candidate expects 0 arguments, 5 provided
minmaxtree.cpp: At global scope:
minmaxtree.cpp:19:8: error: 'query' was not declared in this scope; did you mean 'qry'?
   19 | vector<query> qs[256];
      |        ^~~~~
      |        qry
minmaxtree.cpp:19:13: error: template argument 1 is invalid
   19 | vector<query> qs[256];
      |             ^
minmaxtree.cpp:19:13: error: template argument 2 is invalid
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:124:3: error: 'query' was not declared in this scope; did you mean 'qry'?
  124 |   query q;
      |   ^~~~~
      |   qry
minmaxtree.cpp:125:12: error: 'q' was not declared in this scope
  125 |   char c = q.scan();
      |            ^
minmaxtree.cpp:126:6: warning: array subscript has type 'char' [-Wchar-subscripts]
  126 |   qs[c].push_back(q);
      |      ^
minmaxtree.cpp:126:9: error: request for member 'push_back' in 'qs[((int)c)]', which is of non-class type 'int'
  126 |   qs[c].push_back(q);
      |         ^~~~~~~~~
minmaxtree.cpp:132:15: error: request for member 'begin' in 'qs[109]', which is of non-class type 'int'
  132 |  sort(qs['m'].begin(), qs['m'].end(), [&](const query &x, const query &y) {
      |               ^~~~~
minmaxtree.cpp:132:32: error: request for member 'end' in 'qs[109]', which is of non-class type 'int'
  132 |  sort(qs['m'].begin(), qs['m'].end(), [&](const query &x, const query &y) {
      |                                ^~~
minmaxtree.cpp:132:49: error: 'query' does not name a type; did you mean 'qry'?
  132 |  sort(qs['m'].begin(), qs['m'].end(), [&](const query &x, const query &y) {
      |                                                 ^~~~~
      |                                                 qry
minmaxtree.cpp: In lambda function:
minmaxtree.cpp:134:4: error: expected '{' before ';' token
  134 |  });
      |    ^
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:134:4: error: expected ')' before ';' token
  134 |  });
      |    ^
      |    )
minmaxtree.cpp:132:6: note: to match this '('
  132 |  sort(qs['m'].begin(), qs['m'].end(), [&](const query &x, const query &y) {
      |      ^
minmaxtree.cpp:135:15: error: request for member 'begin' in 'qs[77]', which is of non-class type 'int'
  135 |  sort(qs['M'].begin(), qs['M'].end(), [&](const query &x, const query &y) {
      |               ^~~~~
minmaxtree.cpp:135:32: error: request for member 'end' in 'qs[77]', which is of non-class type 'int'
  135 |  sort(qs['M'].begin(), qs['M'].end(), [&](const query &x, const query &y) {
      |                                ^~~
minmaxtree.cpp:135:49: error: 'query' does not name a type; did you mean 'qry'?
  135 |  sort(qs['M'].begin(), qs['M'].end(), [&](const query &x, const query &y) {
      |                                                 ^~~~~
      |                                                 qry
minmaxtree.cpp: In lambda function:
minmaxtree.cpp:137:4: error: expected '{' before ';' token
  137 |  });
      |    ^
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:137:4: error: expected ')' before ';' token
  137 |  });
      |    ^
      |    )
minmaxtree.cpp:135:6: note: to match this '('
  135 |  sort(qs['M'].begin(), qs['M'].end(), [&](const query &x, const query &y) {
      |      ^
minmaxtree.cpp:138:7: error: 'query' was not declared in this scope; did you mean 'qry'?
  138 |  for (query i : qs['m']) {
      |       ^~~~~
      |       qry
minmaxtree.cpp:143:2: error: expected primary-expression before 'for'
  143 |  for (query i : qs['M']) {
      |  ^~~
minmaxtree.cpp:142:3: error: expected ';' before 'for'
  142 |  }
      |   ^
      |   ;
  143 |  for (query i : qs['M']) {
      |  ~~~
minmaxtree.cpp:143:2: error: expected primary-expression before 'for'
  143 |  for (query i : qs['M']) {
      |  ^~~
minmaxtree.cpp:142:3: error: expected ')' before 'for'
  142 |  }
      |   ^
      |   )
  143 |  for (query i : qs['M']) {
      |  ~~~
minmaxtree.cpp:138:6: note: to match this '('
  138 |  for (query i : qs['m']) {
      |      ^
minmaxtree.cpp:143:12: error: expected ';' before 'i'
  143 |  for (query i : qs['M']) {
      |            ^~
      |            ;
minmaxtree.cpp:148:2: error: expected primary-expression before 'for'
  148 |  for (int i = 2; i <= n; i++) {
      |  ^~~
minmaxtree.cpp:147:3: error: expected ';' before 'for'
  147 |  }
      |   ^
      |   ;
  148 |  for (int i = 2; i <= n; i++) {
      |  ~~~
minmaxtree.cpp:148:2: error: expected primary-expression before 'for'
  148 |  for (int i = 2; i <= n; i++) {
      |  ^~~
minmaxtree.cpp:147:3: error: expected ')' before 'for'
  147 |  }
      |   ^
      |   )
  148 |  for (int i = 2; i <= n; i++) {
      |  ~~~
minmaxtree.cpp:143:6: note: to match this '('
  143 |  for (query i : qs['M']) {
      |      ^
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);
      |  ~~~~~^~~~~~~~~~