Submission #777601

#	Time	Username	Problem	Language	Result	Execution time	Memory
777601		MasterTaster	Senior Postmen (BOI14_postmen)	C++14	55 / 100	637 ms	83908 KiB

postmen

#include <bits/stdc++.h>
 
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
#define MAXN 500003
 
using namespace std;
 
int n, m; //deg[MAXN]
vector<int> put, tren;
set<int> g[MAXN];
bool bio[MAXN];
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>m;
 
	for (int i=0; i<m; i++)
	{
		int u, v; cin>>u>>v;
		g[u].insert(v);
		g[v].insert(u);
		//deg[u]++;
		//deg[v]++;  
	}
	//cout<<"ee"<<endl;
 
	stack<int> st;
	st.push(1);
	while (!st.empty())
	{
		int u=st.top();
		if (g[u].empty())
		{
			put.pb(u);
			st.pop();
			continue;
		}
		int v=(*g[u].begin());
		g[u].erase(v);
		g[v].erase(u);
		//deg[u]--;
		//deg[v]--;
		st.push(v);
	}
 
	//for (auto x:put) cout<<x<<" ";
	//cout<<endl;
 
	for (int i=0; i<put.size(); i++)
	{
		int u=put[i];
		st.push(u);
		if (bio[u])
		{
			tren.clear();
			int nes=0;
			while (!nes || st.top()!=u)
			{
				nes++;
				bio[st.top()]=false;
				tren.pb(st.top());
				st.pop();
			}
			for (auto x:tren) cout<<x<<" ";
			cout<<endl;
		}
		bio[u]=true;
	}
	
	cout<<endl;
 
}

Compilation message (stderr)

postmen.cpp: In function 'int main()':
postmen.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for (int i=0; i<put.size(); i++)
      |                ~^~~~~~~~~~~

• Subtask 1: 38 / 38
• Subtask 2: 17 / 17
• Subtask 3: 0 / 45