oj.uz

Submission #532026

# Submission time Handle Problem Language Result Execution time Memory
532026 2022-03-02T04:00:08 Z hohohaha Min-max tree (BOI18_minmaxtree) C++14
58 / 100
 325 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); 
	}
}

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:109: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]
  109 |   for(; pt[u] < out[u].size(); ++pt[u]) {

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35532 KB Output is correct
2 Correct 18 ms 35548 KB Output is correct
3 Correct 17 ms 35504 KB Output is correct
4 Correct 17 ms 35532 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 72080 KB Output is correct
2 Correct 219 ms 72864 KB Output is correct
3 Correct 196 ms 67332 KB Output is correct
4 Correct 200 ms 72868 KB Output is correct
5 Correct 216 ms 69168 KB Output is correct
6 Correct 182 ms 68940 KB Output is correct
7 Correct 206 ms 65568 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 57740 KB Output is correct
2 Correct 119 ms 57972 KB Output is correct
3 Correct 112 ms 57604 KB Output is correct
4 Correct 112 ms 59428 KB Output is correct
5 Correct 141 ms 58644 KB Output is correct
6 Correct 141 ms 59424 KB Output is correct
7 Correct 139 ms 58400 KB Output is correct
8 Correct 137 ms 58148 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35532 KB Output is correct
2 Correct 18 ms 35548 KB Output is correct
3 Correct 17 ms 35504 KB Output is correct
4 Correct 17 ms 35532 KB Output is correct
5 Correct 182 ms 72080 KB Output is correct
6 Correct 219 ms 72864 KB Output is correct
7 Correct 196 ms 67332 KB Output is correct
8 Correct 200 ms 72868 KB Output is correct
9 Correct 216 ms 69168 KB Output is correct
10 Correct 182 ms 68940 KB Output is correct
11 Correct 206 ms 65568 KB Output is correct
12 Correct 123 ms 57740 KB Output is correct
13 Correct 119 ms 57972 KB Output is correct
14 Correct 112 ms 57604 KB Output is correct
15 Correct 112 ms 59428 KB Output is correct
16 Correct 141 ms 58644 KB Output is correct
17 Correct 141 ms 59424 KB Output is correct
18 Correct 139 ms 58400 KB Output is correct
19 Correct 137 ms 58148 KB Output is correct
20 Runtime error 325 ms 262148 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -