#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(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1040 ms |
13484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1052 ms |
9044 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
