#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
vector <ll> euler;
vector <ll> height;
vector <ll> ind;
vector <ll> parent;
vector <vector<pair<ll,ll>>> st;
vector <vector<ll>> graph;
ll n;
void dfs(ll v = 1, ll p = 0,ll h = 1){
euler.push_back(v);
ind[v] = euler.size()-1;
parent[v] = p;
height[v] = h;
for (int z=0;z<graph[v].size();z++){
if (graph[v][z] == p) continue;
dfs(graph[v][z],v,h+1);
}
euler.push_back(v);
}
void build(){
for (int z=0;z<n;z++){
st[z][0].first = height[z];
st[z][0].second = euler[z];
}
for (int x=1;x<=log2(n);x++){
for (int z=0;z + (1 << (x-1))<n;z++){
if (st[z][x-1].first < st[z + (1 << (x-1))][x-1].first){
st[z][x].second = st[z][x-1].second;
} else {
st[z][x].second = st[z + (1 << (x-1))][x-1].second;
}
st[z][x].first = min(st[z][x-1].first,st[z + (1 << (x-1))][x-1].first);
}
}
}
ll lca(ll x,ll y){
ll k = log2(y-x+1);
pair<ll,ll> temp1 = st[x][k];
pair<ll,ll> temp2 = st[y-(1 << k)+1][k];
if (temp1.first < temp2.first){
return temp1.second;
} else {
return temp2.second;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >>n;
graph.resize(n+1);
parent.resize(n+1,0);
map <pair<ll,ll>,ll> edge;
for (int z=0;z<n-1;z++){
ll a,b;
cin >>a >> b;
graph[a].push_back(b);
}
height.resize(n+1);
ind.resize(n+1);
st.resize(n,vector<pair<ll,ll>>(log2(n)));
dfs();
build();
ll m;
cin >> m;
for (int z=0;z<m;z++){
string a;
cin >> a;
ll u,v,w;
cin >> u >> v >> w;
if (a == "M"){
ll t = lca(min(ind[u],ind[v]),max(ind[u],ind[v]));
while (u != t){
pair <ll,ll> temp;
if (u < parent[u]){
temp = make_pair(u,parent[u]);
} else {
temp = make_pair(parent[u],u);
}
if (!edge[temp]) edge[temp] = w;
edge[temp] = min(edge[temp],w);
u = parent[u];
}
while (v != t){
pair <ll,ll> temp;
if (v < parent[v]){
temp = make_pair(v,parent[v]);
} else {
temp = make_pair(parent[v],v);
}
if (!edge[temp]) edge[temp] = w;
edge[temp] = min(edge[temp],w);
v = parent[v];
}
} else {
ll t = lca(min(ind[u],ind[v]),max(ind[u],ind[v]));
while (u != t){
pair <ll,ll> temp;
if (u < parent[u]){
temp = make_pair(u,parent[u]);
} else {
temp = make_pair(parent[u],u);
}
if (!edge[temp]) edge[temp] = w;
edge[temp] = max(edge[temp],w);
u = parent[u];
}
while (v != t){
pair <ll,ll> temp;
if (v < parent[v]){
temp = make_pair(v,parent[v]);
} else {
temp = make_pair(parent[v],v);
}
if (!edge[temp]) edge[temp] = w;
edge[temp] = max(edge[temp],w);
v = parent[v];
}
}
}
for (auto it = edge.begin();it != edge.end();it++){
cout << (it->first).first << " " << (it->first).second << " " << it->second << endl;
}
}
Compilation message
minmaxtree.cpp: In function 'void dfs(ll, ll, ll)':
minmaxtree.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int z=0;z<graph[v].size();z++){
~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
81 ms |
52216 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
78 ms |
52504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1074 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
