This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define sz(x) (int)((x).size())
#define int long long
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const ll inf = 2e9;
const ll mod = 1e9 + 7;
const int N = 2e6 + 11;
const int X = 1e6;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);
//ifstream in(".in");
//ofstream out(".out");
int depth[N], F[N], l[N], r[N], n, m, k;
int E[N*4], lg[N*4], first[N], viz[N], P[N], dp_min[N], dp_max[N];
vector<int> v[N], g[N];
map<int, int> poz;
pi rmq[30][N];
struct yes{
int tip, x, y, val;
};
yes q[N], w[N];
void dfs(int nod, int p){
E[++k] = nod;
first[nod] = k;
depth[nod] = depth[p] + 1;
F[nod] = P[nod] = p;
for(auto it : v[nod]){
if(it == p)continue;
dfs(it, nod);
E[++k] = nod;
}
}
int get_lca(int x, int y){
int X = first[x], Y = first[y];
if(X > Y)swap(X, Y);
int lvl = lg[Y - X + 1];
pi ans = min(rmq[lvl][X], rmq[lvl][Y - (1 << lvl) + 1]);
return E[ans.ss];
}
int cpl(int nod){
if(viz[nod])return 0;
viz[nod] = 1;
for(auto it : g[nod]){
if(r[it] == 0 || cpl(r[it])){
l[nod] = it;
r[it] = nod;
return 1;
}
}
return 0;
}
void solve(){
cin >> n;
for(int i = 1, x, y; i < n; i++){
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, 0);
for(int i = 1; i <= k; i++){
rmq[0][i] = mp(depth[E[i]], i);
}
for(int i = 1; (1 << i) <= k; i++){
for(int j = 1; j <= k; j++){
rmq[i][j] = rmq[i - 1][j];
if (j + (1 << (i - 1)) <= k && rmq[i - 1][j + (1 << (i - 1))].ff < rmq[i][j].ff)
rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
}
}
for(int i = 2; i <= k; i++){
lg[i] = lg[i / 2] + 1;
}
cin >> m;
int el = 0;
for(int i = 1, x, y, val; i <= m; i++){
char c;
cin >> c >> x >> y >> val;
int type = (c == 'M' ? 1 : 0);
q[i] = {type, x, y, val};
poz[val] = i;
if(type)w[++el] = q[i];
}
sort(w + 1, w + el + 1, [](yes L, yes R){
return L.val < R.val;
});
for(int i = 1; i <= el; i++){
int x = w[i].x, y = w[i].y, val = w[i].val;
int LCA = get_lca(x, y);
for(int I : {x, y}){
int nod = I;
while (nod && depth[nod] > depth[LCA]){
if(!dp_min[nod])dp_min[nod] = val;
int aux = nod;
nod = F[nod];
F[aux] = LCA;
}
}
}
for(int i = 1; i <= n; i++)F[i] = P[i];
el = 0;
for(int i = 1; i <= n; i++){
if(q[i].tip == 0)w[++el] = q[i];
}
sort(w + 1, w + el + 1, [](yes L, yes R){
return L.val < R.val;
});
for(int i = el; i >= 1; i--){
int x = w[i].x, y = w[i].y, val = w[i].val;
int LCA = get_lca(x, y);
for(int I : {x, y}){
int nod = I;
while (nod && depth[nod] > depth[LCA]){
if(!dp_max[nod])dp_max[nod] = val;
int aux = nod;
nod = F[nod];
F[aux] = LCA;
}
}
}
for(int i = 1; i <= n; i++){
if(dp_max[i]){
int idx = poz[dp_max[i]];
g[i].push_back(n + idx);
g[n + idx].push_back (i);
}
if(dp_min[i]){
int idx = poz[dp_min[i]];
g[i].push_back(n + idx);
g[n + idx].push_back(i);
}
}
int ok = 1;
while(ok){
memset(viz, 0, sizeof(viz));
ok = 0;
for(int i = 1; i <= n; i++){
if(!l[i] && cpl(i))ok = 1;
}
}
for(int i = 2; i <= n; i++){
cout << i << ' ' << P[i] << ' ';
int idx = l[i];
cout << (idx ? q[idx - n].val : max(dp_min[i],dp_max[i])) << '\n';
}
}
int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
//cout << setprecision(6) << fixed;
int T = 1;
//cin >> T;
while(T--){
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |