Submission #41288

#	Time	Username	Problem	Language	Result	Execution time	Memory
41288		igzi	Network (BOI15_net)	C++14	100 / 100	913 ms	159164 KiB

net

#include <bits/stdc++.h>
#define maxN 500002

using namespace std;

int n,x,y,i,j,l,t,deg[maxN],br[maxN],par[maxN],a[maxN];
bool visited[maxN];
vector <int> adj[maxN];

void dfs1(int n){
int i;
if(deg[n]==1) br[n]=1;
else br[n]=0;
visited[n]=true;
for(i=0;i<adj[n].size();i++){
if(!visited[adj[n][i]]){
    par[adj[n][i]]=n;
    dfs1(adj[n][i]);
    br[n]+=br[adj[n][i]];
}
}
}
void dfs2(int n){
int i;
visited[n]=true;
if(deg[n]==1) {a[t]=n; t++;}
for(i=0;i<adj[n].size();i++){
    if(!visited[adj[n][i]]){
        dfs2(adj[n][i]);
    }
}
}

int main()
{
    std::ios::sync_with_stdio(false);
    l=0;
    cin>>n;
    for(i=1;i<=n;i++){
        deg[i]=0;
    }
    for(i=1;i<n;i++){
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
        deg[x]++;
        deg[y]++;
    }
    for(i=1;i<=n;i++){
        if(deg[i]==1) l++;
        visited[i]=false;
    }
    par[1]=1;
    dfs1(1);
    for(i=1;i<=n;i++){
        bool b=true;
        if(l-br[i]>l-l/2) continue;
        for(j=0;j<adj[i].size();j++){
            if(adj[i][j]!=par[i]) b=b && (br[adj[i][j]]<=l-l/2);
        }
    if(b) {x=i; break;}
    }
    t=0;
    for(i=1;i<=n;i++){
        visited[i]=false;
    }
    dfs2(x);
    cout<<l-l/2<<endl;
    for(i=0;i<l-l/2;i++){
        cout<<a[i]<<" "<<a[i+l/2]<<endl;
    }
    return 0;
}

Compilation message (stderr)

net.cpp: In function 'void dfs1(int)':
net.cpp:15:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<adj[n].size();i++){
          ^
net.cpp: In function 'void dfs2(int)':
net.cpp:27:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<adj[n].size();i++){
          ^
net.cpp: In function 'int main()':
net.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<adj[i].size();j++){
                  ^

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