oj.uz

Submission #532028

# Submission time Handle Problem Language Result Execution time Memory
532028 2022-03-02T04:02:32 Z hohohaha Min-max tree (BOI18_minmaxtree) C++14
58 / 100
 333 ms 262148 KB 
#include<bits/stdc++.h>

using namespace std;

#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++) 
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define sp ' '
#define endl '\n'
//#define int long long

mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count()); 

const int maxn = 3e5 + 5; 
const int inf = INT_MAX / 2ll; 
int n; 
int m; 
char tp[maxn]; 
int v[maxn]; 
int bg[maxn]; 
int en[maxn]; 
ii E[maxn]; 
vector<ii> g[maxn]; 
set<ii> cur_mx[maxn], cur_mn[maxn]; 
ii mx_mn[maxn], mn_mx[maxn]; 
int ans[maxn]; 
//n - 1 + i, i
struct dinic; 

void merge(set<ii> & des, set<ii> & src) { 
	if(des.size() < src.size()) { 
		des.swap(src); 
	}
	for(auto t: src) { 
		if(!des.count(t)) { 
			des.insert(t); 
		}
		else des.erase(t); 
	}
	src.clear(); 
}

void dfs(int u, int p) { 
	for(ii e: g[u]) { 
		int v = e.fi, id = e.se; 
		if(v - p) { 
			dfs(v,u); 
			if(!cur_mx[v].empty()) { 
				mn_mx[id] = *cur_mx[v].begin(); 
			}
			if(!cur_mn[v].empty()) { 
				mx_mn[id] = *cur_mn[v].rbegin(); 
			}
			merge(cur_mx[u], cur_mx[v]); 
			merge(cur_mn[u], cur_mn[v]); 
		}
	}
}

struct edge { 
	int u, v, c, f; 
	edge(int u, int v, int c) : u(u), v(v), c(c), f(0) {}
	bool full() { 
		return c == f; 
	}
}; 

struct dinic { 
	int num, s, t; 
	vector<edge> E; 
	vector<vi> out; 
	vi dis; 
	vi pt; 
	int f;
	dinic(int _num, int _s, int _t) : num(_num), s(_s), t(_t) { 
		out.resize(num + 5, vi()); 
		dis.resize(num + 5, 0); 
		pt.resize(num + 5, 0); 
		f = 0; 
	}
	void add(int u, int v, int c) { 
		out[u].eb(E.size());
		E.eb(u, v, c); 
		out[v].eb(E.size()); 
		E.eb(v, u, 0); 
	}
	bool bfs() { 
		queue<int> q; 
		fill(begin(dis), end(dis), inf); 
		dis[s] = 0; 
		q.emplace(s); 
		while(q.size()) { 
			int u = q.front(); q.pop(); 
			for(int id: out[u]) {
				int v = E[id].v;  	
				if(!E[id].full() and dis[v] > dis[u] + 1) { 
					dis[v] = dis[u] + 1; 
					q.emplace(v); 
				}
			}
		}
		return dis[t] != inf; 
	}
	int dfs(int u, int cur) { 
		if(u == t) return cur; 
		for(; pt[u] < out[u].size(); ++pt[u]) { 
			int id = out[u][pt[u]]; 
			if(!E[id].full()) { 
				int v = E[id].v; 
				int re = dfs(v, min(cur, E[id].c - E[id].f)); 
				if(re) { 
					E[id].f += re; 
					E[id ^ 1].f -= re; 
					return re; 
				}
			}
		}
		return 0; 
	}
	vector<ii> get_flow() { 
		while(bfs()) { 
			fill(begin(pt), end(pt), 0); 
			while(int re = dfs(s, inf)) { 
				f += re; 
			}
		}
		vector<ii> re; 
		for(auto t: E) { 
			if(t.f > 0 and t.u > 0 and t.u <= n - 1 and t.v > n - 1 and t.v <= n - 1 + m) re.eb( ii(t.u, t.v - (n - 1)) ); 
		}
		return re; 
	}
}; 
signed main() { 
//	freopen("minmaxtree.inp", "r", stdin); 
//	freopen("minmaxtree.out", "w", stdout); 
	ios_base::sync_with_stdio(0);
	cin.tie(0); 
	cout.tie(0); 
	cin >> n; 
	fori(i, 1, n - 1) { 
		int u, v;
		cin >> u >> v; 
		g[u].eb(v, i); 
		g[v].eb(u, i); 
		E[i] = ii(u, v); 
	}
	cin >> m; 
	fori(i, 1, m) { 
		cin >> tp[i] >> bg[i] >> en[i] >> v[i];
		if(tp[i] == 'M') { 
			cur_mx[bg[i]].insert(ii(v[i], i));
			cur_mx[en[i]].insert(ii(v[i], i)); 
		}
		else { 
			cur_mn[bg[i]].insert(ii(v[i], i)); 
			cur_mn[en[i]].insert(ii(v[i], i)); 
		}
	}
	dfs(1, 1); 
	dinic D(n - 1 + m + 2, 0, n - 1 + m + 1); 
	fori(i, 1, n - 1) { 	
		D.add(0, i, 1);
	}
	fori(i, n - 1 + 1, n - 1 + m) { 
		D.add(i, n - 1 + m + 1, 1); 
	}
	fori(i, 1, n - 1) { 
		if(mn_mx[i].se != 0) { 
			D.add(i, mn_mx[i].se + n - 1, 1); 
		}
		if(mx_mn[i].se != 0) { 
			D.add(i, mx_mn[i].se + n - 1, 1); 
		}
	}
	auto temp = D.get_flow(); 
	for(auto t: temp) { 
		ans[t.fi] = v[t.se];
	}
	fori(i, 1, n - 1) { 
		if(!ans[i]) { 
			if(mn_mx[i].se) ans[i] = mn_mx[i].fi; 
			else if(mx_mn[i].se) ans[i] = mx_mn[i].fi; 
			else ans[i] = 1; 
		}
		cout << E[i].fi << sp << E[i].se << sp << ans[i] << endl; 
	}
}

Compilation message

minmaxtree.cpp: In member function 'int dinic::dfs(int, int)':
minmaxtree.cpp:110:15: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for(; pt[u] < out[u].size(); ++pt[u]) {

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35532 KB Output is correct
2 Correct 18 ms 35484 KB Output is correct
3 Correct 18 ms 35552 KB Output is correct
4 Correct 18 ms 35544 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 63824 KB Output is correct
2 Correct 279 ms 60304 KB Output is correct
3 Correct 196 ms 60524 KB Output is correct
4 Correct 201 ms 64988 KB Output is correct
5 Correct 227 ms 60460 KB Output is correct
6 Correct 184 ms 61116 KB Output is correct
7 Correct 207 ms 60212 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 55348 KB Output is correct
2 Correct 139 ms 55444 KB Output is correct
3 Correct 117 ms 56136 KB Output is correct
4 Correct 120 ms 57872 KB Output is correct
5 Correct 141 ms 56464 KB Output is correct
6 Correct 138 ms 56752 KB Output is correct
7 Correct 137 ms 55564 KB Output is correct
8 Correct 177 ms 55588 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35532 KB Output is correct
2 Correct 18 ms 35484 KB Output is correct
3 Correct 18 ms 35552 KB Output is correct
4 Correct 18 ms 35544 KB Output is correct
5 Correct 185 ms 63824 KB Output is correct
6 Correct 279 ms 60304 KB Output is correct
7 Correct 196 ms 60524 KB Output is correct
8 Correct 201 ms 64988 KB Output is correct
9 Correct 227 ms 60460 KB Output is correct
10 Correct 184 ms 61116 KB Output is correct
11 Correct 207 ms 60212 KB Output is correct
12 Correct 116 ms 55348 KB Output is correct
13 Correct 139 ms 55444 KB Output is correct
14 Correct 117 ms 56136 KB Output is correct
15 Correct 120 ms 57872 KB Output is correct
16 Correct 141 ms 56464 KB Output is correct
17 Correct 138 ms 56752 KB Output is correct
18 Correct 137 ms 55564 KB Output is correct
19 Correct 177 ms 55588 KB Output is correct
20 Runtime error 333 ms 262148 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -