제출 #68888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68888		MatheusLealV	어르신 집배원 (BOI14_postmen)	C++17	55 / 100	562 ms	89956 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];

bool dfs(int x, int ini, int f)
{
	//cout<<"DFS "<<x<<"\n";
	usado[x] = id;

	for(auto v: grafo[x])
	{
		if(v.f == ini and !block[v.s])
		{
			block[v.s] = 1;

			// cout<<"PROX "<<x<<" "<<"-1\n";

			prox[x] = -1;

			return true;
		}

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

		//cout<<"DFS "<<x<<" to "<<v.f<<"\n";

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

			// cout<<"PROX "<<x<<" "<<v.f<<"\n";

			block[v.s] = 1;

			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++)
	{
		for(auto v: grafo[x])
		{
			if(block[v.s]) continue;

			++id;

			usado[x] = id;

			block[v.s] = 1;

			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";
	}
}

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