Submission #74638

#	Time	Username	Problem	Language	Result	Execution time	Memory
74638		Vardanyan	Network (BOI15_net)	C++14	0 / 100	13 ms	12288 KiB

net

//#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
using namespace std;
const int N = 500*1000+7;
vector<int> g[N];
bool c[N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
        if(x == 1) c[y] = 1;
        if(y == 1) c[x] = 1;
    }
    vector<int> leaf;
    for(int i = 2;i<=n;i++){
        if(g[i].size() == 1) leaf.push_back(i);
    }
    bool f = false;
    for(int i = 0;i<leaf.size();i++) if(!c[leaf[i]]) f = true;
    if(!f){
        cout<<leaf.size()-1<<endl;
        for(int i = 0;i<leaf.size()-1;i++) cout<<leaf[i]<<" "<<leaf[i+1]<<endl;
        return 0;
    }
    if(leaf.size() == 1){
        cout<<1<<endl;
        cout<<1<<" "<<leaf[0]<<endl;
        return 0;
    }
    int u;
    for(int i = 0;i<leaf.size();i++) if(!c[leaf[i]]) u = leaf[i];
    if(leaf.size() == 2){
        cout<<2<<endl;
        cout<<leaf[0]<<" "<<leaf[1]<<endl;
        cout<<1<<" "<<u<<endl;
        return 0;
    }
    for(int i = 0;i<leaf.size();i++){
        if(leaf[i] == u){
            leaf.erase(leaf.begin()+i);
            break;
        }
    }
    cout<<leaf.size()<<endl;
    for(int i = 0;i<leaf.size()-1;i++) cout<<leaf[i]<<" "<<leaf[i+1]<<endl;
    cout<<1<<" "<<u<<endl;
    return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<leaf.size();i++) if(!c[leaf[i]]) f = true;
                   ~^~~~~~~~~~~~
net.cpp:26:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<leaf.size()-1;i++) cout<<leaf[i]<<" "<<leaf[i+1]<<endl;
                       ~^~~~~~~~~~~~~~
net.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<leaf.size();i++) if(!c[leaf[i]]) u = leaf[i];
                   ~^~~~~~~~~~~~
net.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<leaf.size();i++){
                   ~^~~~~~~~~~~~
net.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<leaf.size()-1;i++) cout<<leaf[i]<<" "<<leaf[i+1]<<endl;
                   ~^~~~~~~~~~~~~~
net.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
net.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~

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