oj.uz

Submission #859509

# Submission time Handle Problem Language Result Execution time Memory
859509 2023-10-10T09:13:04 Z 1075508020060209tc Min-max tree (BOI18_minmaxtree) C++14
29 / 100
 417 ms 73052 KB 
#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];
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{
            ans[eid]=rmp[v];
            hs[v]=1;
        }
    }
}


for(int nw=1;nw<=Q;nw++){
    if(vvis[nw]){continue;}
    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;
        if(hs[nw]==0){
            ans[eid]=rmp[nw];
            hs[nw]=1;
        }else{
            ans[eid]=rmp[v];
            hs[v]=1;
        }
    }
}
for(int i=1;i<=n-1;i++){
    cout<<ar[i]<<" "<<br[i]<<" "<<ans[i]<<endl;
}


}

Compilation message

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 'int main()':
minmaxtree.cpp:238: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]
  238 |     for(int i=0;i<ne[nw].size();i++){
      |                 ~^~~~~~~~~~~~~~
minmaxtree.cpp:260: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]
  260 |     for(int i=0;i<ne[nw].size();i++){
      |                 ~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 49756 KB Output is correct
2 Correct 7 ms 49756 KB Output is correct
3 Correct 9 ms 49756 KB Output is correct
4 Correct 8 ms 50012 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 70608 KB Output is correct
2 Correct 417 ms 73052 KB Output is correct
3 Correct 325 ms 68116 KB Output is correct
4 Correct 321 ms 70776 KB Output is correct
5 Correct 330 ms 69856 KB Output is correct
6 Correct 319 ms 67484 KB Output is correct
7 Correct 350 ms 66080 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 60876 KB Output is correct
2 Correct 212 ms 61040 KB Output is correct
3 Correct 236 ms 62524 KB Output is correct
4 Correct 213 ms 64580 KB Output is correct
5 Correct 224 ms 61424 KB Output is correct
6 Correct 232 ms 62224 KB Output is correct
7 Correct 241 ms 60912 KB Output is correct
8 Incorrect 258 ms 60732 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 49756 KB Output is correct
2 Correct 7 ms 49756 KB Output is correct
3 Correct 9 ms 49756 KB Output is correct
4 Correct 8 ms 50012 KB Output is correct
5 Correct 383 ms 70608 KB Output is correct
6 Correct 417 ms 73052 KB Output is correct
7 Correct 325 ms 68116 KB Output is correct
8 Correct 321 ms 70776 KB Output is correct
9 Correct 330 ms 69856 KB Output is correct
10 Correct 319 ms 67484 KB Output is correct
11 Correct 350 ms 66080 KB Output is correct
12 Correct 205 ms 60876 KB Output is correct
13 Correct 212 ms 61040 KB Output is correct
14 Correct 236 ms 62524 KB Output is correct
15 Correct 213 ms 64580 KB Output is correct
16 Correct 224 ms 61424 KB Output is correct
17 Correct 232 ms 62224 KB Output is correct
18 Correct 241 ms 60912 KB Output is correct
19 Incorrect 258 ms 60732 KB Output isn't correct
20 Halted 0 ms 0 KB -