제출 #896095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
896095		I_am_Polish_Girl	Senior Postmen (BOI14_postmen)	C++14	38 / 100	1057 ms	16100 KiB

postmen

	/*
	* powered by ANDRIY POPYK
	* in honor of  SEGMENT DECOMPOSITION and N ^ (log(N)) and hate_club_Dasha_Lobas
	* I hate GeZhiyuan
	* fuck you
	*/

	/*
	#pragma GCC optimize("Ofast")
	#pragma GCC target("avx,avx2,fma")
	#pragma GCC optimization("unroll-loops")
	#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")
	*/


	#include <algorithm>
	#include <cmath>
	#include <cstdio>
	#include <iostream>
	#include <map>
	#include <set>
	#include <bitset>
	#include <queue>
	#include <string>
	#include <vector>
	#include <stack>
	#include <random>
	#include <ctime>
	#include <iomanip>
	#include <unordered_map>
	#include <unordered_set>

	using namespace std;
	typedef long long ll;
	int mod = 998244353;
	int inf = 2000000000000000000;

	vector <vector <int>> g;

	int edges[1000000];
	int ind_ed[1000000];
	bool t[1000000];
	vector <int> el;


	void dfs(int ind)
	{
		while (ind_ed[ind] < g[ind].size())
		{
			int i = g[ind][ind_ed[ind]];
			ind_ed[ind]++;
			if (t[i] == true)
				continue;

			t[i] = true;
			t[i ^ 1] = true;
			dfs(edges[i]);
		}
		el.push_back(ind);
	}


	signed main() {
		int times_ = 1;

		//cin >> times_;

		while (times_--)
		{
			int n, m;
			cin >> n >> m;
			g.resize(n);

			for (int i = 0; i < m; i++)
			{
				int u, v;
				
				scanf("%d%d", &u, &v);
				u--;
				v--;
				g[u].push_back(2 * i);
				g[v].push_back(2 * i+1);

				edges[2 * i]= v;

				edges[2 * i+1] = u;

			}
		
			dfs(0);
		
			vector <int> s(n+1);
			for (int i = 0; i < el.size(); i++) 
			{
				if (s[el[i]] == 0)
				{
					s[el[i]]++;
				}
				else
				{
					int ind = i - 1;
					while (s[el[i]] > 0)
					{
						if (s[el[ind]] > 0)
						{
							el[ind] += 1;
							printf("%d ", el[ind]);
							el[ind]--;
						}

						s[el[ind]] = 0;

						ind--;
					}

					printf("\n");

					s[el[i]]++;
				}
			}

		
		}
	}
	/*
	axbbbbbbzbxbbabaxbbabababababababaababababababababaabababababababxbxbb
	5
	ababb
	bbb
	tr
	are
	aaa
	*/
	/*

	4
	12
	1 1 1 2 2 3 4 4 7 7 6
	11 2 1 11 12 8 5 8 8 5 11 7
	13
	1 1 1 2 2 2 3 3 4 5 6 6
	2 2 2 1 4 9 7 2 5 2 1 11 2
	7
	1 1 2 2 3 3
	6 5 2 3 6 5 6
	*/

컴파일 시 표준 에러 (stderr) 메시지

postmen.cpp:36:12: warning: overflow in conversion from 'long int' to 'int' changes value from '2000000000000000000' to '1321730048' [-Woverflow]
   36 |  int inf = 2000000000000000000;
      |            ^~~~~~~~~~~~~~~~~~~
postmen.cpp: In function 'void dfs(int)':
postmen.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   while (ind_ed[ind] < g[ind].size())
      |          ~~~~~~~~~~~~^~~~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |    for (int i = 0; i < el.size(); i++)
      |                    ~~^~~~~~~~~~~
postmen.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~

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