Submission #68889

#	Time	Username	Problem	Language	Result	Execution time	Memory
68889		MatheusLealV	Senior Postmen (BOI14_postmen)	C++17	38 / 100	1091 ms	34008 KiB

postmen

#include <bits/stdc++.h>
#define N 500050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, m, block[N], cnt = 0, usado[N], prox[N], id = 1;

vector<pii> grafo[N];

vector<int> path[N];

inline bool dfs(int x, int &ini, int &f)
{
	usado[x] = id;

	for(int i = 0; i < grafo[x].size(); i++)
	{
		auto v = grafo[x][i];

		if(block[v.s])
		{
			swap(grafo[x][i], grafo[x].back());

			grafo[x].pop_back();

			i --;

			continue;
		}

		if(v.f == ini and !block[v.s])
		{
			block[v.s] = 1;

			prox[x] = -1;

			swap(grafo[x][i], grafo[x].back());

			grafo[x].pop_back();

			return true;
		}

		if(usado[v.f] == id or block[v.s]) continue;

		if(dfs(v.f, ini, f))
		{
			prox[x] = v.f;

			block[v.s] = 1;

			swap(grafo[x][i], grafo[x].back());

			grafo[x].pop_back();

			return true;
		}
	}

	return false;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m;

	for(int i = 1, a, b; i <= m; i++)
	{
		cin>>a>>b;

		grafo[a].push_back({b, i});

		grafo[b].push_back({a, i});
	}

	for(int x = 1; x <= n; x++) random_shuffle(grafo[x].begin(), grafo[x].end());

	for(int x = 1; x <= n; x++)
	{
		for(int i = 0; i < grafo[x].size(); i++)
		{
			auto v = grafo[x][i];

			if(block[v.s])
			{
				swap(grafo[x][i], grafo[x].back());

				grafo[x].pop_back();

				i --;

				continue;
			}

			++id;

			usado[x] = id;

			block[v.s] = 1;

			swap(grafo[x][i], grafo[x].back());

			grafo[x].pop_back();

			i --;

			path[cnt].push_back(x);

			if(dfs(v.f, x, cnt))
			{
				int u = v.f;

				while(u != -1)
				{					
					path[cnt].push_back(u);

					u = prox[u];
				}

				++ cnt;
			}
		}
	}

	for(int i = 0; i < cnt; i++)
	{
		for(auto x: path[i]) cout<<x<<" ";

		cout<<"\n";
	}
}

Compilation message (stderr)

postmen.cpp: In function 'bool dfs(int, int&, int&)':
postmen.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < grafo[x].size(); i++)
                 ~~^~~~~~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < grafo[x].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~

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