oj.uz

답안 #861466

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861466 2023-10-16T09:30:52 Z iskhakkutbilim Min-max tree (BOI18_minmaxtree) C++17
0 / 100
 1000 ms 13484 KB 
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 1e9 + 7;
const int N = 1e5;
struct edge{
	int a, b, w;
};
int n;
vector<pair<int, int> > g[N+10];
pair<int, int> value[N + 10], E[N + 10];
int ans[N + 10];
vector<int> ve, ve1;
void dfs(int v, int par, int dest){
	if(v == dest){
		ve1 = ve;
		return;
	}
	for(auto [to, idx] : g[v]){
		if(to == par) continue;
		ve.push_back(idx);
		dfs(to, v, dest);
		ve.pop_back();
	}
}

/*
11
1 3
1 2
1 5
3 4
2 6
2 7
5 11
7 8
8 9
8 10
2
M 1 10 50
m 1 2 1
*/



main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1;i < n; i++){
		value[i] = {-1, -1};
		ans[i] = -1;
		int a, b; cin >> a >> b;
		E[i] = {a, b};
		g[a].push_back({b, i});
		g[b].push_back({a, i});
	}
	int q; cin >> q;
	vector<edge> high, low;
	set<int> W;
	for(int i = 0;i < q; i++){
		char ch; cin >> ch;
		int a, b, w; cin >> a >> b >> w;
		if(ch == 'M') high.push_back({a, b, w});
		else low.push_back({a, b, w});
	}
	sort(all(low), [&](edge A, edge B){
		return A.w > B.w;	
	});
	sort(all(high), [&](edge A, edge B){
		return A.w < B.w;	
	});
	for(auto [a, b, w] : high){
		ve.clear();
		ve1.clear();
		dfs(a, a, b);
		for(int idx : ve1){
			if(value[idx].ss == -1 or value[idx].ss > w)  value[idx].ss = w;
		}
	}
	for(auto [a, b, w] : low){
		ve.clear();
		ve1.clear();
		dfs(a, a, b);
		for(int idx : ve1){
			if(value[idx].ff == -1 or value[idx].ff < w)  value[idx].ff = w;
		}
	}
	set<int> st;
	for(int i = 1;i < n; i++){
		if(value[i].ff == -1 && value[i].ss == -1){
			ans[i] = 0;
			continue;
		}
	}
	for(int i = 1;i < n; i++){
		if(ans[i] != -1) continue;
		if(value[i].ff == -1) ans[i] = value[i].ss;
		else if(value[i].ss == -1) ans[i] = value[i].ff;
		
		st.insert(ans[i]);
	}
	for(int i = 1;i < n; i++){
		if(ans[i] != -1) continue;
		if(value[i].ff != -1 && st.count(value[i].ff) == false){
			st.insert(value[i].ff);
			ans[i] = value[i].ff;
		}else if(value[i].ss != -1 && st.count(value[i].ss) == false){
			st.insert(value[i].ss);
			ans[i] = value[i].ss;
		}else{
			ans[i] = (value[i].ss == -1 ? value[i].ff : value[i].ss);
		}
	}
	for(int i = 1;i < n; i++){
		cout << E[i].ff << ' ' << E[i].ss << ' ';
		cout << ans[i] << '\n';
	}
	return 0;
}

Compilation message

minmaxtree.cpp:49:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   49 | main(){
      | ^~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1040 ms 13484 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1052 ms 9044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

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