제출 #532026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532026		hohohaha	Min-max tree (BOI18_minmaxtree)	C++14	58 / 100	325 ms	262148 KiB

minmaxtree

#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; 
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 7
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 0 / 42