Submission #860075

#	Time	Username	Problem	Language	Result	Execution time	Memory
860075		1075508020060209tc	Min-max tree (BOI18_minmaxtree)	C++14	22 / 100	393 ms	117500 KiB

minmaxtree

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;int Q;
int ar[100005];
int br[100005];
vector<int>e[70005];
vector<int>mxq[70005];
vector<int>mnq[70005];
vector<int>dmx[70005];
vector<int>dmn[70005];
int mxlm[70005];
int mnlm[70005];
char typ[70005];int ina[100005];int inb[100005];int inz[100005];
int jmp[20][100005];
int dph[100005];
void fdfs(int nw,int pa){
jmp[0][nw]=pa;
dph[nw]=dph[pa]+1;
for(int i=0;i<e[nw].size();i++){
    int id=e[nw][i];
    int v=ar[id]^br[id]^nw;
    if(v==pa){continue;}
    fdfs(v,nw);
}
}
int lca(int a,int b){
if(a==b){return a;}
if(dph[a]>dph[b]){swap(a,b);}
for(int i=19;i>=0;i--){
    if(dph[jmp[i][b]]>=dph[a]){
        b=jmp[i][b];
    }
}
if(a==b){return a;}
for(int i=19;i>=0;i--){
    if(jmp[i][a]!=jmp[i][b]){
        a=jmp[i][a];b=jmp[i][b];
    }
}
return jmp[0][a];
}

multiset<int>mxdp[70005];
multiset<int>mndp[70005];
void dfs(int nw,int pa,int paid){
if(e[nw].size()==1&&nw!=1){
    for(int i=0;i<mxq[nw].size();i++){
        mxdp[nw].insert(mxq[nw][i]);
    }
    if(mxdp[nw].size()){
        mxlm[paid]=*(mxdp[nw].begin());
    }
    return;
}

int zo=nw^ar[e[nw][0]]^br[e[nw][0]];
for(int i=0;i<e[nw].size();i++){
    int id=e[nw][i];
    int v=ar[id]^br[id]^nw;
    if(v==pa){continue;}
    dfs(v,nw,id);
    if(mxdp[v].size()>mxdp[zo].size()){
        zo=v;
        swap(e[nw][0],e[nw][i]);
    }
}
swap(mxdp[nw],mxdp[zo]);
for(int i=1;i<e[nw].size();i++){
    int id=e[nw][i];
    int v=ar[id]^br[id]^nw;
    if(v==pa){continue;}
    for(auto it=mxdp[v].begin();it!=mxdp[v].end();it++){
        mxdp[nw].insert((*it));
    }
}
for(int i=0;i<mxq[nw].size();i++){
    mxdp[nw].insert(mxq[nw][i]);
}
for(int i=0;i<dmx[nw].size();i++){
    mxdp[nw].erase(mxdp[nw].find(dmx[nw][i]));
    mxdp[nw].erase(mxdp[nw].find(dmx[nw][i]));
}
if(mxdp[nw].size()){
    mxlm[paid]=*(mxdp[nw].begin());
}
}

void dfs2(int nw,int pa,int paid){
if(e[nw].size()==1&&nw!=1){
    for(int i=0;i<mnq[nw].size();i++){
        mndp[nw].insert(mnq[nw][i]);
    }
    if(mndp[nw].size()){
        mnlm[paid]=*(mndp[nw].rbegin());
    }
    return;
}

int zo=nw^ar[e[nw][0]]^br[e[nw][0]];
for(int i=0;i<e[nw].size();i++){
    int id=e[nw][i];
    int v=ar[id]^br[id]^nw;
    if(v==pa){continue;}
    dfs2(v,nw,id);
    if(mndp[v].size()>mndp[zo].size()){
        zo=v;
        swap(e[nw][0],e[nw][i]);
    }
}
swap(mndp[nw],mndp[zo]);
for(int i=1;i<e[nw].size();i++){
    int id=e[nw][i];
    int v=ar[id]^br[id]^nw;
    if(v==pa){continue;}
    for(auto it=mndp[v].begin();it!=mndp[v].end();it++){
        mndp[nw].insert((*it));
    }
}
for(int i=0;i<mnq[nw].size();i++){
    mndp[nw].insert(mnq[nw][i]);
}
for(int i=0;i<dmn[nw].size();i++){
    mndp[nw].erase(mndp[nw].find(dmn[nw][i]));
    mndp[nw].erase(mndp[nw].find(dmn[nw][i]));
}
if(mndp[nw].size()){
    mnlm[paid]=*(mndp[nw].rbegin());
}
}

void build(){
fdfs(1,0);
for(int i=1;i<=19;i++){
    for(int j=1;j<=n;j++){
        jmp[i][j]=jmp[i-1][jmp[i-1][j]];
    }
}
for(int i=1;i<=Q;i++){
    if(typ[i]=='M'){
        mxq[ina[i]].push_back(inz[i]);
        mxq[inb[i]].push_back(inz[i]);
        dmx[lca(ina[i],inb[i])].push_back(inz[i]);
    }else{
        mnq[ina[i]].push_back(inz[i]);
        mnq[inb[i]].push_back(inz[i]);
        dmn[lca(ina[i],inb[i])].push_back(inz[i]);
    }
}
for(int i=1;i<=n-1;i++){
    mxlm[i]=1e12;
    mnlm[i]=-mxlm[i];
}
dfs(1,0,0);
dfs2(1,0,0);
}
map<int,int>mp;int rmp[200005];
void lisanhua(){
vector<int>vc;
for(int i=1;i<=Q;i++){
    vc.push_back(inz[i]);
}
sort(vc.begin(),vc.end());
for(int i=0;i<Q;i++){
    mp[vc[i]]=i+1;
    rmp[i+1]=vc[i];
}
}
int vis[200005];
int hs[200005];
int ans[200005];
int dgr[200005];
int vvis[200005];
vector<pair<int,int>>ne[200005];
int rt;int rte;
void adfs1(int nw,int pa){
vvis[nw]=1;
if(hs[nw]){rt=nw;}
for(int i=0;i<ne[nw].size();i++){
    int eid=ne[nw][i].second;
    if(vis[eid]){continue;}
    int v=ne[nw][i].first;
    if(vvis[v]&&rt==0){
        ans[eid]=rmp[nw];
        rt=nw;
        vis[eid]=1;
    }
    if(vvis[v]){continue;}
    adfs1(v,nw);
}
}
void adfs2(int nw,int pa,int paid){
ans[paid]=rmp[nw];
vvis[nw]=2;
for(int i=0;i<ne[nw].size();i++){
    int eid=ne[nw][i].second;
    if(vis[eid]){continue;}
    int v=ne[nw][i].first;
    if(vvis[nw]!=2){
        vis[eid]=1;
        adfs2(v,nw,eid);
        continue;
    }
    //ans[eid]=rmp[nw];
    vis[eid]=1;
}

}

signed main(){
cin>>n;
for(int i=1;i<=n-1;i++){
    cin>>ar[i]>>br[i];
    e[ar[i]].push_back(i);
    e[br[i]].push_back(i);
}
cin>>Q;
for(int i=1;i<=Q;i++){
    cin>>typ[i]>>ina[i]>>inb[i]>>inz[i];
}
build();/*
for(int i=1;i<=n-1;i++){
    cout<<mnlm[i]<<" "<<mxlm[i]<<endl;
}*/
lisanhua();


for(int i=1;i<=n-1;i++){
    int cnt=0;
    if(mnlm[i]<=1e9&&mnlm[i]>=-1e9){
        //mnlm[i]=mp[mnlm[i]];
        cnt++;
    }
    if(mxlm[i]<=1e9&&mxlm[i]>=-1e9){
       // mxlm[i]=mp[mxlm[i]];
        cnt++;
    }
    if(cnt==0){
        ans[i]=1e9;
        continue;
    }
    if(cnt==1){
        if(abs(mxlm[i])<=1e9){
            vis[i]=1;
            hs[mp[mxlm[i]]]=1;
            ans[i]=mxlm[i];
        }else{
            vis[i]=1;
            hs[mp[mnlm[i]]]=1;
            ans[i]=mnlm[i];
        }
        continue;
    }
    ne[mp[mxlm[i]]].push_back({mp[mnlm[i]],i});
    ne[mp[mnlm[i]]].push_back({mp[mxlm[i]],i});
    dgr[mp[mxlm[i]]]++;
    dgr[mp[mnlm[i]]]++;
}/*
for(int i=1;i<=n-1;i++){
    cout<<mnlm[i]<<" "<<mxlm[i]<<endl;
}*/
queue<int>q;
for(int i=1;i<=Q;i++){
    if(dgr[i]==1){
        q.push(i);
    }
}

while(q.size()){
    int nw=q.front();
    q.pop();
    vvis[nw]=1;
    for(int i=0;i<ne[nw].size();i++){
        int eid=ne[nw][i].second;
        if(vis[eid]){continue;}
        int v=ne[nw][i].first;
        vis[eid]=1;
        dgr[v]--;
        if(dgr[v]==1){
            q.push(v);
        }
        if(hs[nw]==0){
            ans[eid]=rmp[nw];
            hs[nw]=1;
        }else{
            assert(0);
            ans[eid]=rmp[v];
            hs[v]=1;
        }
    }
}

for(int i=1;i<=Q;i++){
    if(vvis[i]){continue;}
    rt=0;
    adfs1(i,0);
    adfs2(rt,0,0);
}



for(int i=1;i<=n-1;i++){
    cout<<ar[i]<<" "<<br[i]<<" "<<ans[i]<<endl;
}


}

Compilation message (stderr)

minmaxtree.cpp: In function 'void fdfs(long long int, long long int)':
minmaxtree.cpp:20:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dfs(long long int, long long int, long long int)':
minmaxtree.cpp:48:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i=0;i<mxq[nw].size();i++){
      |                 ~^~~~~~~~~~~~~~~
minmaxtree.cpp:58:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
minmaxtree.cpp:69:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 | for(int i=1;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
minmaxtree.cpp:77:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 | for(int i=0;i<mxq[nw].size();i++){
      |             ~^~~~~~~~~~~~~~~
minmaxtree.cpp:80:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 | for(int i=0;i<dmx[nw].size();i++){
      |             ~^~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void dfs2(long long int, long long int, long long int)':
minmaxtree.cpp:91:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i=0;i<mnq[nw].size();i++){
      |                 ~^~~~~~~~~~~~~~~
minmaxtree.cpp:101:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
minmaxtree.cpp:112:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 | for(int i=1;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
minmaxtree.cpp:120:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 | for(int i=0;i<mnq[nw].size();i++){
      |             ~^~~~~~~~~~~~~~~
minmaxtree.cpp:123:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 | for(int i=0;i<dmn[nw].size();i++){
      |             ~^~~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void adfs1(long long int, long long int)':
minmaxtree.cpp:179:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 | for(int i=0;i<ne[nw].size();i++){
      |             ~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'void adfs2(long long int, long long int, long long int)':
minmaxtree.cpp:195:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 | for(int i=0;i<ne[nw].size();i++){
      |             ~^~~~~~~~~~~~~~
minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:273:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  273 |     for(int i=0;i<ne[nw].size();i++){
      |                 ~^~~~~~~~~~~~~~

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