Submission #1098034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098034		AndrijaM	Network (BOI15_net)	C++17	63 / 100	693 ms	262144 KiB

net

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=150;
const int mod=998244353;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ///freopen("lexicografic.in","r",stdin);
    ///freopen("lexicografic.out","w",stdout);
    int n;
    cin>>n;
    vector<int>g[n];
    set<int>st;
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        a--;b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i=0;i<n;i++)
    {
        if(g[i].size()==1)
        {
            st.insert(i);
        }
    }
    int mi[n][n];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            mi[i][j]=1e18;
        }
    }
    vector<pair<int,pair<int,int>>>v;
    for(int i=0;i<n;i++)
    {
        queue<int>Q;
        Q.push(i);
        Q.push(1);
        bool vis[n];
        memset(vis,0,sizeof vis);
        vis[i]=true;
        while(!Q.empty())
        {
            int node=Q.front();Q.pop();
            int k=Q.front();Q.pop();
            mi[i][node]=k;
            if(st.count(i)==1 && st.count(node)==1 && i!=node)
            v.push_back({k,{i,node}});
            for(auto ax:g[node])
            {
                if(vis[ax])continue;
                Q.push(ax);
                Q.push(k+1);
                vis[ax]=1;
            }
        }
    }
    int sz=st.size();
    int kol=0;
    bool p[n];
    memset(p,0,sizeof p);
    sort(v.rbegin(),v.rend());
    vector<pair<int,int>>ans;
    int num;
    for(auto ax:v)
    {
        int w=ax.first;
        int a=ax.second.first;
        int b=ax.second.second;
        ///cout<<w<<endl;
        if(a==b)continue;
        if(st.count(a)==0 || st.count(b)==0)continue;
        if(p[a]==0 && p[b]==0)
        {
            p[a]=p[b]=1;
            kol+=2;
            num=a+1;
            st.erase(a);
            st.erase(b);
            ans.push_back({a+1,b+1});
            continue;
        }
    }
    if(sz%2==1)
    {
        ans.push_back({*st.begin()+1,num});
    }
    cout<<ans.size()<<endl;
    for(auto ax:ans)
    {
        cout<<ax.first<<" "<<ax.second<<endl;
    }
    return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:76:13: warning: unused variable 'w' [-Wunused-variable]
   76 |         int w=ax.first;
      |             ^
net.cpp:34:9: warning: variable 'mi' set but not used [-Wunused-but-set-variable]
   34 |     int mi[n][n];
      |         ^~

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