oj.uz

답안 #896164

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
896164 2023-12-31T23:37:58 Z I_am_Polish_Girl 어르신 집배원 (BOI14_postmen) C++14
55 / 100
 500 ms 120068 KB 
/*
* 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;

#define int long long
int mod = 998244353;
int inf = 2000000000000000000;

vector <vector <int>> g;

vector <pair <int, int>> edges;
vector <int> ind_ed;
vector <bool> t;
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].second);
	}


	el.push_back(ind);
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int times_ = 1;

	//cin >> times_;

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

		for (int i = 0; i < m; i++)
		{
			int u, v;
			cin >> u >> v;
			u--;
			v--;
			g[u].push_back(2 * i);
			g[v].push_back(2 * i + 1);

			edges.push_back({ u , v });
			edges.push_back({ v , u });

		}

		t.resize(edges.size(), false);

		dfs(0);

		set <int> s;

		vector <int> go_to(el.size(), inf);
		for (int i = 0; i < el.size(); i++)
		{
			if (s.count(el[i]) == 0)
			{
				s.insert(el[i]);
			}
			else
			{
				int ind = i - 1;
				while (s.count(el[i]) > 0)
				{
					if (s.count(el[ind]) > 0)
						cout << el[ind] + 1 << " ";

					s.erase(el[ind]);

					ind--;

					if (ind < 0)
						break;
					ind = min(ind, go_to[ind]);

					if (ind < 0)
						break;
				}

				go_to[i - 1] = ind;

				cout << "\n";

				s.insert(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
*/

Compilation message

postmen.cpp: In function 'void dfs(long long int)':
postmen.cpp:50:21: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  while (ind_ed[ind] < g[ind].size())
postmen.cpp: In function 'int main()':
postmen.cpp:102:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for (int i = 0; i < el.size(); i++)
      |                   ~~^~~~~~~~~~~

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 7 ms 2636 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 44 ms 13892 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 51 ms 14876 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 7 ms 2640 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 46 ms 13884 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 51 ms 14448 KB Output is correct
13 Correct 93 ms 23228 KB Output is correct
14 Correct 63 ms 16328 KB Output is correct
15 Correct 43 ms 18652 KB Output is correct
16 Correct 77 ms 24848 KB Output is correct
17 Correct 53 ms 12636 KB Output is correct
18 Correct 80 ms 17956 KB Output is correct

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 7 ms 2640 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 46 ms 14648 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 52 ms 14744 KB Output is correct
13 Correct 75 ms 23516 KB Output is correct
14 Correct 72 ms 16248 KB Output is correct
15 Correct 43 ms 18688 KB Output is correct
16 Correct 78 ms 24060 KB Output is correct
17 Correct 56 ms 12480 KB Output is correct
18 Correct 81 ms 17976 KB Output is correct
19 Execution timed out 645 ms 120068 KB Time limit exceeded
20 Halted 0 ms 0 KB -