oj.uz

답안 #859520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
859520 2023-10-10T09:18:27 Z 1075508020060209tc Min-max tree (BOI18_minmaxtree) C++14
29 / 100
 386 ms 70780 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];
    assert(1);
}
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:239: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]
  239 |     for(int i=0;i<ne[nw].size();i++){
      |                 ~^~~~~~~~~~~~~~
minmaxtree.cpp:261: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]
  261 |     for(int i=0;i<ne[nw].size();i++){
      |                 ~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 49756 KB Output is correct
2 Correct 8 ms 49828 KB Output is correct
3 Correct 7 ms 49756 KB Output is correct
4 Correct 8 ms 49756 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 386 ms 68128 KB Output is correct
2 Correct 328 ms 70780 KB Output is correct
3 Correct 317 ms 65992 KB Output is correct
4 Correct 347 ms 68208 KB Output is correct
5 Correct 329 ms 67836 KB Output is correct
6 Correct 374 ms 65056 KB Output is correct
7 Correct 320 ms 63652 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 59392 KB Output is correct
2 Correct 215 ms 59656 KB Output is correct
3 Correct 218 ms 61328 KB Output is correct
4 Correct 219 ms 63544 KB Output is correct
5 Correct 224 ms 59936 KB Output is correct
6 Correct 236 ms 60724 KB Output is correct
7 Correct 235 ms 59492 KB Output is correct
8 Incorrect 229 ms 59384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 49756 KB Output is correct
2 Correct 8 ms 49828 KB Output is correct
3 Correct 7 ms 49756 KB Output is correct
4 Correct 8 ms 49756 KB Output is correct
5 Correct 386 ms 68128 KB Output is correct
6 Correct 328 ms 70780 KB Output is correct
7 Correct 317 ms 65992 KB Output is correct
8 Correct 347 ms 68208 KB Output is correct
9 Correct 329 ms 67836 KB Output is correct
10 Correct 374 ms 65056 KB Output is correct
11 Correct 320 ms 63652 KB Output is correct
12 Correct 207 ms 59392 KB Output is correct
13 Correct 215 ms 59656 KB Output is correct
14 Correct 218 ms 61328 KB Output is correct
15 Correct 219 ms 63544 KB Output is correct
16 Correct 224 ms 59936 KB Output is correct
17 Correct 236 ms 60724 KB Output is correct
18 Correct 235 ms 59492 KB Output is correct
19 Incorrect 229 ms 59384 KB Output isn't correct
20 Halted 0 ms 0 KB -