Submission #126230

#	Time	Username	Problem	Language	Result	Execution time	Memory
126230		Vardanyan	Network (BOI15_net)	C++14	100 / 100	1241 ms	70272 KiB

net

#include <bits/stdc++.h>
using namespace std;
const int N = 500*1000+5;
vector<int> g[N];
bool used[N];
int timer, tin[N], fup[N];
bool f = false;
void dfs (int v, int p = -1) {
	used[v] = true;
	tin[v] = fup[v] = timer++;
	for (size_t i=0; i<g[v].size(); ++i) {
		int to = g[v][i];
		if (to == p)  continue;
		if (used[to])
			fup[v] = min (fup[v], tin[to]);
		else {
			dfs (to, v);
			fup[v] = min (fup[v], fup[to]);
			if (fup[to] > tin[v])
				f = true;
		}
	}
}
int n;
void find_bridges() {
	timer = 0;
	f = false;
	memset(tin,0,sizeof(tin));
	memset(fup,0,sizeof(fup));
	for (int i=1; i<=n; ++i)
		used[i] = false;
	for (int i=1; i<=n; ++i)
		if (!used[i])
			dfs (i);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i = 1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vector<int> lf;
    for(int i = 1;i<=n;i++){
        if(g[i].size() == 1) lf.push_back(i);
    }
    /*
    cout<<(lf.size()+1)/2<<endl;
    for(int i = 0;i<lf.size()-1;i+=2){
        cout<<lf[i]<< " "<<lf[i+1]<<endl;
    }
    if(lf.size()%2){
        cout<<lf[lf.size()-1]<<" "<<lf[lf.size()-2]<<endl;
    }*/
    int tim = 50;
    while(tim--){
        random_shuffle(lf.begin(),lf.end());
        //cout<<(lf.size()+1)/2<<endl;
        for(int i = 0;i<lf.size()-1;i+=2){
            //cout<<lf[i]<< " "<<lf[i+1]<<endl;
            g[lf[i]].push_back(lf[i+1]);
            g[lf[i+1]].push_back(lf[i]);
        }
        if(lf.size()%2){
        //    cout<<lf[lf.size()-1]<<" "<<lf[lf.size()-2]<<endl;
            g[lf[lf.size()-1]].push_back(lf[lf.size()-2]);
            g[lf[lf.size()-2]].push_back(lf[lf.size()-1]);
        }
        find_bridges();
        if(!f){
            cout<<(lf.size()+1)/2<<endl;
            for(int i = 0;i<lf.size()-1;i+=2){
                cout<<lf[i]<< " "<<lf[i+1]<<endl;
            }
            if(lf.size()%2){
                cout<<lf[lf.size()-1]<<" "<<lf[lf.size()-2]<<endl;
            }
            return 0;
        }
         for(int i = 0;i<lf.size()-1;i+=2){
            //cout<<lf[i]<< " "<<lf[i+1]<<endl;
            g[lf[i]].pop_back();
            g[lf[i+1]].pop_back();
        }
        if(lf.size()%2){
        //    cout<<lf[lf.size()-1]<<" "<<lf[lf.size()-2]<<endl;
            g[lf[lf.size()-1]].pop_back();
            g[lf[lf.size()-2]].pop_back();
        }
    }
    return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:61:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<lf.size()-1;i+=2){
                       ~^~~~~~~~~~~~
net.cpp:74:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0;i<lf.size()-1;i+=2){
                           ~^~~~~~~~~~~~
net.cpp:82:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          for(int i = 0;i<lf.size()-1;i+=2){
                        ~^~~~~~~~~~~~

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