| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 137648 | mechfrog88 | Min-max tree (BOI18_minmaxtree) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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> index;
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);
index[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);
index.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(index[u],index[v]),max(index[u],index[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(index[u],index[v]),max(index[u],index[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;
}
}