oj.uz

답안 #254173

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
254173 2020-07-29T12:48:20 Z Saboon Min-max tree (BOI18_minmaxtree) C++14
0 / 100
 240 ms 30200 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 70000 + 20;

int E1[maxn], E2[maxn], W[maxn], c[maxn];
vector<int> t[maxn], g[maxn];
set<pair<int,int>> mn[maxn], mx[maxn];
char Qtype[maxn];
int Qv[maxn], Qu[maxn], Qz[maxn], p[maxn];
bool visited[maxn];
int match[maxn], fmatch[maxn];

bool dfs(int v){
	if (visited[v] or fmatch[v] != -1)
		return 0;
	visited[v] = 1;
	for (auto u : g[v]){
		if (match[u] == -1 or dfs(match[u])){
			fmatch[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}

void dfssack(int v, int par = -1){
	p[v] = par;
	for (auto u : t[v]){
		if (u == par)
			continue;
		dfssack(u,v);
		if (mx[c[u]].size() + mn[c[u]].size() > mx[c[v]].size() + mn[c[u]].size())
			swap(c[v],c[u]);
		for (auto it : mn[c[u]]){
			if (mn[c[v]].find(it) != mn[c[v]].end())
				mn[c[v]].erase(it);
			else
				mn[c[v]].insert(it);
		}
		for (auto it : mx[c[u]]){
			if (mx[c[v]].find(it) != mx[c[v]].end())
				mx[c[v]].erase(it);
			else
				mx[c[v]].insert(it);
		}
		mn[c[u]].clear(), mx[c[u]].clear();
	}
	if (!mx[c[v]].empty()){
		int idx = (*mx[c[v]].begin()).second;
		g[v].push_back(idx);
		W[v] = Qz[idx];
	}
	if (!mn[c[v]].empty()){
		int idx = (*mn[c[v]].begin()).second;
		g[v].push_back(idx);
		W[v] = Qz[idx];
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 1; i <= n-1; i++){
		cin >> E1[i] >> E2[i];
		t[E1[i]].push_back(E2[i]);
		t[E2[i]].push_back(E1[i]);
	}
	for (int i = 1; i <= n; i++)
		c[i] = i;
	int q;
	cin >> q;
	for (int i = 1; i <= q; i++){
		cin >> Qtype[i] >> Qv[i] >> Qu[i] >> Qz[i];
		if (Qtype[i]){
			mn[c[Qv[i]]].insert({-Qz[i],i});
			mn[c[Qu[i]]].insert({-Qz[i],i});
		}
		else{
			mx[c[Qv[i]]].insert({+Qz[i],i});
			mx[c[Qu[i]]].insert({+Qz[i],i});
		}
	}
	dfssack(1);
	int maxMatch = 0;
	memset(match, -1, sizeof match);
	memset(fmatch, -1, sizeof fmatch);
	while (true){
		memset(visited, 0, sizeof visited);
		int pre = maxMatch;
		for (int i = 1; i <= n; i++)
			maxMatch += dfs(i);
		if (pre == maxMatch)
			break;
	}
	for (int i = 1; i <= q; i++)
		W[match[i]] = Qz[i];
	for (int i = 2; i <= n; i++)
		cout << p[i] << " " << i << " " << W[i] << '\n'; 
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 10880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 240 ms 30200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 101 ms 19832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 10880 KB Output isn't correct
2 Halted 0 ms 0 KB -