Submission #1191581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191581		12345678	Min-max tree (BOI18_minmaxtree)	C++20	0 / 100	115 ms	26748 KiB

minmaxtree

#include <bits/stdc++.h>

using namespace std;

const int nx=7e4+5, kx=17;

int n, k, u[nx], v[nx], x, y, w[nx], lvl[nx], pa[nx][kx], mn[nx], mx[nx], sz[nx];
char opr;
vector<int> d[nx], addmn[nx], remmn[nx], addmx[nx], remmx[nx];
multiset<pair<int ,int>> msmx, msmn;

int lca(int u, int v)
{
    if (lvl[u]>lvl[v]) swap(u, v);
    for (int i=kx-1; i>=0; i--) if (lvl[pa[v][i]]>=lvl[u]) v=pa[v][i];
    if (u==v) return u;
    for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
    return pa[u][0];
}

void dfs(int u, int p)
{
    lvl[u]=lvl[p]+1;
    pa[u][0]=p;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    for (auto v:d[u]) if (v!=p) dfs(v, u);
}

void dfssz(int u, int p)
{
    sz[u]=1+addmn[u].size()+remmn[u].size()+addmx[u].size()+remmx[u].size();
    for (auto v:d[u]) if (v!=p) dfssz(v, u), sz[u]+=sz[v];
}

void dfsadd(int u, int p)
{
    for (auto v:d[u]) if (v!=p) dfsadd(v, u);
    for (auto x:addmn[u]) msmn.insert({w[x], x});
    for (auto x:remmn[u]) msmn.erase(msmn.find({w[x], x}));
    for (auto x:addmx[u]) msmx.insert({w[x], x});
    for (auto x:remmx[u]) msmx.erase(msmx.find({w[x], x}));
}

void sack(int u, int p, bool rem)
{
    pair<int, int> hv;
    for (auto v:d[u]) if (v!=p) hv=max(hv, {sz[v], v});
    for (auto v:d[u]) if (v!=p&&v!=hv.second) sack(v, u, 1);
    if (hv.second) sack(hv.second, u, 0);
    for (auto v:d[u]) if (v!=p&&v!=hv.second) dfsadd(v, u);
    for (auto x:addmn[u]) msmn.insert({w[x], x});
    for (auto x:remmn[u]) msmn.erase(msmn.find({w[x], x}));
    for (auto x:addmx[u]) msmx.insert({w[x], x});
    for (auto x:remmx[u]) msmx.erase(msmx.find({w[x], x}));
    mx[u]=mn[u]=1;
    //cout<<"debug "<<u<<' '<<msmx.size()<<'\n';
    if (!msmx.empty()) mx[u]=prev(msmx.end())->first;
    if (!msmn.empty()) mn[u]=msmn.begin()->first;
    if (rem) msmx.clear(), msmn.clear();
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<n; i++) cin>>u[i]>>v[i], d[u[i]].push_back(v[i]), d[v[i]].push_back(u[i]);
    dfs(1, 1);
    cin>>k;
    for (int i=1; i<=k; i++) 
    {
        cin>>opr>>x>>y>>w[i];
        int l=lca(x, y);
        if (opr=='M') addmx[x].push_back(i), addmx[y].push_back(i), remmx[l].push_back(i), remmx[l].push_back(i);
        else addmn[x].push_back(i), addmn[y].push_back(i), remmn[l].push_back(i), remmn[l].push_back(i);
    }
    dfssz(1, 1);
    sack(1, 1, 0);
    //for (int i=2; i<=n; i++) cout<<i<<' '<<pa[i][0]<<' '<<mx[i]<<'\n';
    for (int i=1; i<n; i++) cout<<u[i]<<' '<<v[i]<<' '<<((lvl[u[i]]>lvl[v[i]])?mx[u[i]]:mx[v[i]])<<'\n';
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42