Submission #605890

#	Time	Username	Problem	Language	Result	Execution time	Memory
605890		buidangnguyen05	Network (BOI15_net)	C++14	0 / 100	3 ms	3860 KiB

net

#include <bits/stdc++.h>
#include <algorithm>
#include <queue>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fori(x,a,b) for(int x=a;x<=b;x++)
#define ford(x,a,b) for(int x=a;x>=b;x--)
#define forv(a,b) for(auto&a:b)

#define fi first
#define se second
//#define int long long
#define pb push_back

#define ll long long
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()

#define reset(f,x) memset(f,x,sizeof(f))
#define getbit(x,i) ((x>>(i))&1)
#define batbit(x,i) (x|(1ll<<(i)))
#define tatbit(x,i) (x&~(1<<(i)))


using namespace std;
const int N = 5e4+ 5;
vector<pair<int,int> > a[N];
vector <int> b[N];
int parent[N], num[N], tout[N], low[N];
int ttime = 0;
int bridge[N], c[N], jointCnt = 0, bridgeCnt = 0;
int n, m, comp = 0;
int scc;
vector<int> bi[N];
stack<int> st;
int id[N];

void dfs(int u, int pre)
{
    low[u] = num[u] = ++ttime;
    st.push(u);
    int child = 0;
    for (auto e: a[u]){
    	int v = e.first;
    	int t = e.second;
    	if (pre == t) continue;
        if (!num[v]){
			parent[v] = u;
			dfs(v,t);
			low[u] = min(low[u], low[v]);
			child++;

			// Checking bridge
			if (low[v] == num[v]){
				bridge[v]++;
			}
        }
        else{
            low[u] = min(low[u], num[v]);
        }
	}
    if (num[u] == low[u]){
	    scc++;
        int v;
        do{
            v = st.top();
            id[v] = scc;
            bi[scc].push_back(v);
            st.pop();
        }
        while (v != u);
    }
}



signed main()
{
//    freopen("task.inp","r",stdin);
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin >> n; m = n - 1;
	fori(i,1,m)
	{
	    int u, v;
		cin >> u >> v;
		a[u].push_back({v, i});
		a[v].push_back({u, i});
	}
	num[0] = 1e9;

	fori(i,1,n)
		if (num[i] == 0) dfs(i,0);
	fori(i,1,n)
	{
		if (bridge[i]){
			b[parent[i]].push_back(i);
			b[i].push_back(parent[i]);
		}
	}

	int cnt = 0;
	vector<int> ans;

	fori(i,1,n)
		if (b[i].size() == 1 && (bi[id[i]].size() == 1)) ans.push_back(i);
	if (ans.size() == 0) return cout << 0, 0;
	if (ans.size() == 1)
		fori(i,1,n)
			if (ans[0] != i) return cout << 1 << "\n" << i << " " << ans[0] << "\n", 0;

	cout << (ans.size() + 1)/2 << "\n";
	ans.push_back(ans[0]);
	for (int i = 0; i < ans.size() - 1; i += 2){
		cout << ans[i] << " " << ans[i + 1] << "\n";
	}
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:117:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |  for (int i = 0; i < ans.size() - 1; i += 2){
      |                  ~~^~~~~~~~~~~~~~~~
net.cpp:105:6: warning: unused variable 'cnt' [-Wunused-variable]
  105 |  int cnt = 0;
      |      ^~~

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