Submission #414363

#	Time	Username	Problem	Language	Result	Execution time	Memory
414363		bigDuck	Network (BOI15_net)	C++14	0 / 100	21 ms	35532 KiB

net

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll

int n;

vector<int> g[500010];
bool v[500010];
int r=0;
int dp[500010][3];
int lf[500010];

vector<pii> e[500010][2];

int rl1=0, rl2=0;



void dfs(int s){
    v[s]=true;
    //cout<<s<<" "<<flush;
    for(auto u:g[s]){
        if(!v[u]){
            dfs(u);
        }
    }

    if(g[s].size()==1){
        dp[s][0]=1; dp[s][1]=0;
        lf[s]=s;
        v[s]=false;
        return;
    }

    int sum=0;
    vector<pii> vec; vec.clear();
    for(auto u:g[s]){
        if(!v[u]){
            sum+=dp[u][0];
            vec.pb({dp[u][1]-dp[u][0], u});
        }
    }

    sort(vec.begin(), vec.end());
    for(int i=0; i<=vec.size(); i+=2){
        if(i==0){
            dp[s][0]=min(dp[s][0], sum);
        }
        else{
            sum+=vec[i-1].ft+vec[i-2].ft+1;
        }
        dp[s][0]=min(dp[s][0], sum);
    }
    sum=0;
    for(auto u:g[s]){
        if(!v[u]){
            sum+=dp[u][0];
        }
    }
    /*
    if(vec.empty()){
            cout<<g[s].size()<<"p ";
        cout<<"badd"<<flush;
        return;
    }
    */
    sum+=vec[0].ft;
    for(int i=1; i<=vec.size(); i+=2){
        if(i==1){
            dp[s][1]=min(dp[s][1], sum);
        }
        else{
            sum+=vec[i-1].ft+vec[i-2].ft+1;
        }
        dp[s][1]=min(dp[s][1], sum);
    }
    lf[s]=lf[vec[0].sc ];






    v[s]=false;
    return;
}



int mrk[500010];
int united[500010];

void dfs2(int s){
    v[s]=true;
    int sum=0;
    vector<pii> vec;
    for(auto u:g[s]){
        if(!v[u]){
            sum+=dp[u][0];
            vec.pb({dp[u][1]-dp[u][0], u});
        }
    }
    sort(vec.begin(), vec.end());

    if(g[s].size()==1){
        if( (mrk[s]==0) && (!united[s]) ){
            if(s==rl1){
                    united[s]=true; united[rl2]=true;
                cout<<s<<" "<<rl2<<"\n";
            }
            else{
                united[s]=true; united[rl1]=true;
                cout<<s<<" "<<rl1<<"\n";
            }
        }
        else{
            ;
        }
        return ;
    }


    if(mrk[s]==0){

        for(int i=0; i<=vec.size(); i+=2){
            if(sum==dp[s][0]){
                for(int j=i-2; j>=2; j-=2){
                        if(!united[lf[vec[j-1].sc ] ] || !united[lf[vec[j-2].sc ] ] ){
                    cout<<lf[vec[j-1].sc ]<<" "<<lf[vec[j-2].sc ]<<"\n";
                    mrk[vec[j-1].sc ]=mrk[vec[j-2].sc ]=1;
                    united[lf[vec[j-1].sc ] ]=united[lf[vec[j-2].sc ] ]=1;
                    }
                }
                break;
            }

            if(i==0){
                ;
            }
            else{
                sum+=vec[i-1].ft+vec[i-2].ft+1;
            }

            if(sum==dp[s][0]){
                for(int j=i; j>=2; j-=2){
                     if(!united[lf[vec[j-1].sc ] ] || !united[lf[vec[j-2].sc ] ] ){
                    cout<<lf[vec[j-1].sc ]<<" "<<lf[vec[j-2].sc ]<<"\n";
                    mrk[vec[j-1].sc ]=mrk[vec[j-2].sc ]=1;
                    united[lf[vec[j-1].sc ] ]=united[lf[vec[j-2].sc ] ]=1;
                    }
                }
                break;
            }

        }

    }
    else{
        sum+=vec[0].ft;
        for(int i=1; i<=vec.size(); i+=2){
            if(sum==dp[s][1]){
                for(int j=i-2; j>=3; j-=2){
                     if(!united[lf[vec[j-1].sc ] ] || !united[lf[vec[j-2].sc ] ] ){
                    cout<<lf[vec[j-1].sc ]<<" "<<lf[vec[j-2].sc ]<<"\n";
                    mrk[vec[j-1].sc ]=mrk[vec[j-2].sc ]=1;
                    united[lf[vec[j-1].sc ] ]=united[lf[vec[j-2].sc ] ]=1;
                    }
                }
                break;
            }

            if(i==1){
                ;
            }
            else{
                sum+=vec[i-1].ft+vec[i-2].ft+1;
            }

            if(sum==dp[s][1]){
                for(int j=i; j>=3; j-=2){
                     if(!united[lf[vec[j-1].sc ] ] || !united[lf[vec[j-2].sc ] ] ){
                    cout<<lf[vec[j-1].sc ]<<" "<<lf[vec[j-2].sc ]<<"\n";
                    mrk[vec[j-1].sc ]=mrk[vec[j-2].sc ]=1;
                    united[lf[vec[j-1].sc ] ]=united[lf[vec[j-2].sc ] ]=1;
                    }
                }
                break;
            }

        }

    }

    for(auto u:g[s]){
        if(!v[u]){
            dfs2(u);
        }
    }

    return;
}





int32_t main(){
INIT
cin>>n;
for(int i=1; i<n; i++){
    int a, b;
    cin>>a>>b;
    g[a].pb(b);
    g[b].pb(a);
    dp[i][0]=dp[i][1]=dp[i][2]=1e9;
}
dp[n][0]=dp[n][1]=dp[n][2]=1e9;


for(int i=1; i<=n; i++){
    if(g[i].size()==1){
        if(rl1>0){
            rl2=i; break;
        }
        else{
            rl1=i;
        }
    }
}


int s=0;
for(int i=1; i<=n; i++){
    if(g[i].size()>1){
        r=i;
        dfs(i);
        break;
    }
}
cout<<dp[r][0]<<"\n";
dfs2(r);


return 0;
}

Compilation message (stderr)

net.cpp: In function 'void dfs(int)':
net.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0; i<=vec.size(); i+=2){
      |                  ~^~~~~~~~~~~~
net.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=1; i<=vec.size(); i+=2){
      |                  ~^~~~~~~~~~~~
net.cpp: In function 'void dfs2(int)':
net.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for(int i=0; i<=vec.size(); i+=2){
      |                      ~^~~~~~~~~~~~
net.cpp:168:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |         for(int i=1; i<=vec.size(); i+=2){
      |                      ~^~~~~~~~~~~~
net.cpp: In function 'int32_t main()':
net.cpp:240:5: warning: unused variable 's' [-Wunused-variable]
  240 | int s=0;
      |     ^

• Subtask 1: 0 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37