oj.uz

답안 #861394

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861394 2023-10-16T05:35:42 Z iskhakkutbilim Min-max tree (BOI18_minmaxtree) C++17
0 / 100
 1000 ms 14380 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();
	}
}
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;
	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] : low){
		ve.clear();
		ve1.clear();
		dfs(a, a, b);
		for(int idx : ve1){
			value[idx].ff = w;
		}
	}
	
	for(auto [a, b, w] : high){
		ve.clear();
		ve1.clear();
		dfs(a, a, b);
		for(int idx : ve1){
			value[idx].ss = w;
		}
	}
	set<int> st;
	for(int i = 1;i < n; i++){
		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;
		}
	}
	for(int i = 1;i < n; i++){
		if(ans[i] == -1){
//			cout << value[i].ff << " , " << value[i].ss << " = ";
			for(int k = (value[i].ff == -1 ? 0 : value[i].ff); k <= (value[i].ss == -1 ? N : value[i].ss); k++){
				if(st.count(k) == false){
					st.insert(k);
					ans[i] = k;
					break;
				}
			}
		}
	}
	for(int i = 1;i < n; i++){
		cout << E[i].ff << ' ' << E[i].ss << ' ';
		cout << ans[i] << '\n';
	}
	return 0;
}

Compilation message

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

Subtask #1
0 / 7.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 42.0

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