oj.uz

답안 #312466

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
312466 2020-10-13T12:47:49 Z mosiashvililuka Training (IOI07_training) C++17
100 / 100
 61 ms 8724 KB 
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,jm,pi,dep[1009],msh[1009][14],lf[1009],rg[1009],tim,lc,dp[1009],dp2[1009][1009],dpk[1009][2109],nmb[1009];
pair <pair <int, int>, int> p[5009];
vector <pair <pair <int, int>, pair <int, int> > > vv[1009];
vector <int> vvl[1009],vvvl[1009];
vector <pair <int, int> > vvv[1009];
vector <int> v[1009];
void dfs(int q, int w){
    dep[q]=dep[w]+1;
    msh[q][0]=w;
    for(int h=1; h<=12; h++) msh[q][h]=msh[msh[q][h-1]][h-1];
    tim++;
    lf[q]=rg[q]=tim;
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it)==w) continue;
        dfs((*it),q);
        if(rg[q]<rg[(*it)]) rg[q]=rg[(*it)];
    }
}
bool anc(int q, int w){
    if(lf[q]<=lf[w]&&rg[q]>=rg[w]) return 1; else return 0;
}
int lca(int q, int w){
    if(anc(q,w)) return q;
    if(anc(w,q)) return w;
    for(int h=12; h>=0; h--){
        if(msh[q][h]!=0&&anc(msh[q][h],w)==0) q=msh[q][h];
    }
    return msh[q][0];
}
int lca2(int q, int w){
    for(int h=12; h>=0; h--){
        if(msh[q][h]!=0&&anc(msh[q][h],w)==0) q=msh[q][h];
    }
    return q;
}
void dfs2(int q, int w){
    if(v[q].size()==1&&w!=0){
        return;
    }
    dp[q]=0;
    int zu=0;
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it)==w) continue;
        zu++;
        nmb[(*it)]=zu-1;
        dfs2((*it),q);
        dp[q]+=dp[(*it)];
    }
    dpk[q][0]=dp[q];
    int sh=v[q].size();
    if(q!=1) sh--;
    for(int h=1; h<(1<<sh); h++){
        int hh=0;
        for(hh=0; hh<sh; hh++){
            if((h&(1<<hh))!=0){
                if(dpk[q][h]<dpk[q][(h^(1<<hh))]) dpk[q][h]=dpk[q][(h^(1<<hh))];
            }
        }
        hh=-1;
        for(vector <pair <int, int> >::iterator it=vvv[q].begin(); it!=vvv[q].end(); it++){
            hh++;
            if((h&(1<<nmb[(*it).second]))==0) continue;
            zx=dpk[q][(h^(1<<nmb[(*it).second]))]+max(0,dp2[(*it).second][(*it).first]-dp[(*it).second]+vvvl[q][hh]);
            /*if(q==1){
                cout<<vvvl[q].size()<<endl;
                cout<<(*it).first<<" ka "<<(*it).second<<" "<<zx<<"    "<<vvvl[q][hh]<<endl;
            }*/
            if(dpk[q][h]<zx) dpk[q][h]=zx;
        }
        hh=-1;
        for(vector <pair <pair <int, int>, pair <int, int> > >::iterator it=vv[q].begin(); it!=vv[q].end(); it++){
            hh++;
            if((h&(1<<nmb[(*it).first.second]))==0||(h&(1<<nmb[(*it).second.second]))==0) continue;
            zx=dpk[q][(h^((1<<nmb[(*it).first.second])|(1<<nmb[(*it).second.second])))]+max(0,dp2[(*it).first.second][(*it).first.first]-dp[(*it).first.second]+dp2[(*it).second.second][(*it).second.first]-dp[(*it).second.second]+vvl[q][hh]);
            if(dpk[q][h]<zx) dpk[q][h]=zx;
        }
    }
    zx=(1<<sh)-1;
    if(dp[q]<dpk[q][zx]) dp[q]=dpk[q][zx];
    dp2[q][q]=dp[q];
    for(i=1; i<=a; i++){
        if(anc(q,i)==0||q==i) continue;
        xc=lca2(i,q);
        dp2[q][i]=dp2[xc][i]+dpk[q][(zx^(1<<nmb[xc]))]-dp[xc];
    }
    //cout<<q<<"   "<<dp[q]<<endl;
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>b;
    for(i=1; i<=b; i++){
        cin>>c>>d>>e;
        jm+=e;
        if(e==0){
            v[c].push_back(d);
            v[d].push_back(c);
        }else{
            pi++;
            p[pi].first.first=c;
            p[pi].first.second=d;
            p[pi].second=e;
        }
    }
    dfs(1,0);
    for(i=1; i<=pi; i++){
        c=p[i].first.first;d=p[i].first.second;e=p[i].second;
        lc=lca(c,d);
        if((dep[c]+dep[d]-dep[lc]*2)%2==1) continue;
        if(anc(c,d)){
            vvv[c].push_back(make_pair(d,lca2(d,c)));
            vvvl[c].push_back(e);
            continue;
        }
        if(anc(d,c)){
            vvv[d].push_back(make_pair(c,lca2(c,d)));
            vvvl[d].push_back(e);
            continue;
        }
        vv[lc].push_back(make_pair(make_pair(c,lca2(c,d)),make_pair(d,lca2(d,c))));
        vvl[lc].push_back(e);
    }
    dfs2(1,0);
    /*cout<<dp2[2][3]<<" "<<dp[2];
    cout<<endl<<endl;*/
    cout<<jm-dp[1];
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 512 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 8696 KB Output is correct
2 Correct 61 ms 8696 KB Output is correct

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 640 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 768 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 896 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1408 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1792 KB Output is correct
2 Correct 4 ms 1536 KB Output is correct
3 Correct 9 ms 2944 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 4608 KB Output is correct
2 Correct 13 ms 2176 KB Output is correct
3 Correct 8 ms 3072 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 1280 KB Output is correct
2 Correct 6 ms 3072 KB Output is correct
3 Correct 23 ms 8576 KB Output is correct
4 Correct 7 ms 3328 KB Output is correct

Subtask #11
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 4608 KB Output is correct
2 Correct 48 ms 8724 KB Output is correct
3 Correct 16 ms 3584 KB Output is correct
4 Correct 13 ms 3024 KB Output is correct