Submission #777630

#	Time	Username	Problem	Language	Result	Execution time	Memory
777630		MasterTaster	Senior Postmen (BOI14_postmen)	C++14	100 / 100	465 ms	44812 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 500010

using namespace std;

int n, m; //deg[MAXN]
vector<int> put, tren;
vector<pii> g[MAXN];
bool bio[MAXN], bila[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].pb({v, i});
		g[v].pb({u, i});
		//deg[u]++;
		//deg[v]++;  
	}
	//cout<<"ee"<<endl;

	stack<int> st;
	st.push(1);
	while (!st.empty())
	{
		int u=st.top();

		pii nesto=g[u].back();
		while (g[u].size() && bila[nesto.yy])
		{
			g[u].pop_back();
			nesto=g[u].back();
		}

		if (!g[u].size())
		{
			put.pb(u);
			st.pop();
			continue;
		}

		nesto=g[u].back();
		bila[nesto.yy]=true;
		g[u].pop_back();
		//deg[u]--;
		//deg[v]--;
		int v=nesto.xx;
		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:63:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for (int i=0; i<put.size(); i++)
      |                ~^~~~~~~~~~~

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