Submission #1048470

# Submission time Handle Problem Language Result Execution time Memory
1048470 2024-08-08T07:49:30 Z ksun69(#11093) Make them Meet (EGOI24_makethemmeet) C++17
53.2829 / 100
141 ms 14928 KB
#include <bits/stdc++.h>
using namespace std;

// D. Make Them Meet
// Problem Name makethemmeet
// Time Limit 9 seconds
// Memory Limit 1 gigabyte
// Mila and Laura have been friends online for a long time; they have never met in real life. Currently,
// they are both attending the same onsite event, which means that they will surely meet. However,
// the hotel where they both are staying is very big and confusing. Therefore, after several days, they
// still have not run into each other.
// The hotel consists of N rooms, numbered 0 to N − 1. Each room has a lamp that can be changed
// into different colours. You have found the electrical service room of the hotel, allowing you to alter
// the colours of the lamps. Your goal is to guide Mila and Laura using the lamps to finally make them
// meet.
// The hotel can be represented as a graph with N vertices (the rooms) and M edges (the corridors
// connecting the rooms). Mila and Laura initially start in two different rooms but you do not know
// which ones. You can make a number of moves. Each move consists of printing a list of N integers,
// c , c ,..., c , meaning that the colour of the lamp in room i becomes c for every
// i = 0, 1,..., N − 1. Mila and Laura will then look at the colour of the lamp in the room they are
// currently in and walk to a neighbouring room whose lamp has the same colour. If there is no such
// neighbouring room, they will stay where they are. If there are several such neighbouring rooms,
// they will choose one arbitrarily.
// If Mila and Laura are in the same room or use the same corridor simultaneously at any point
// during your moves, you have succeeded in making them meet. You can make at most 20 000
// moves, but you will get a higher score if you use fewer moves.
// Note that you do not know which rooms Mila and Laura start in or how they walk if they have
// multiple rooms with the same colour to choose from. Your solution must be correct regardless
// of their starting rooms or how they walk.
// Input
// 0 1 N−1 i
// makethemmeet (1 of 4) 
// The first line contains two integers, N and M, the number of rooms and the number of corridors
// in the hotel respectively.
// The following M lines each contain two integers, u and v , meaning that rooms u and v are
// connected by a corridor.
// Output
// Print one line with an integer K, the number of moves.
// On each of the following K lines, print N integers, c , c ,..., c , such that 0 ≤ c ≤ N for all i.
// These K lines represent your moves in the chronological order.
// Constraints and Scoring
// 2 ≤ N ≤ 100.
// N − 1 ≤ M ≤ .
// 0 ≤ u , v ≤ N − 1, and u ≠ v .
// You can reach every room from every other room. Furthermore, there are no corridors going
// from a room to itself, and there are not multiple corridors between any pair of rooms.
// You may use at most 20 000 moves (that is, K ≤ 20 000).
// Your solution will be tested on a set of test groups, each worth a number of points. Each test group
// contains a set of test cases. To get the points for a test group, you need to solve all test cases in the
// test group.

namespace std {

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

} // namespace std

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int N, M;
	cin >> N >> M;
	vector<vector<int> > adj(N);
	vector<pair<int, int> > edges;
	bool is_path = true;
	bool is_star = true;
	bool is_complete = (M == N*(N-1)/2);
	bool is_tree = (M == N-1);
	for(int i = 0; i < M; i++){
		int u, v;
		cin >> u >> v;
		if(abs(u-v) != 1) is_path = false;
		if(u != 0 && v != 0) is_star = false;
		edges.push_back({u, v});
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	vector<vector<int> > state(N, vector<int>(N, 1));

	for(int i = 0; i < N; i++){ state[i][i] = 0; }

	vector<vector<int> > queries;
	if(is_path){
	for(int i = 0; i < 2*N; i++){
		vector<int> c(N, 0);
			for(int j = 0; j < N; j++){
				c[j] = ((i + j) % 4) / 2;
			}
			queries.push_back(c);
		}
	} else if (is_star){
		queries.push_back(vector<int>(N, 1));
		for(int i = 0; i < N; i++){
			vector<int> c(N, 0);
			c[i] = c[0] = 1;
			queries.push_back(c);
			queries.push_back(c);
		}
	} else if(is_complete){
		for(int s = 0; s < N; s++){
			vector<int> c(N, 0);
			for(int i = 0; i < N; i++){
				int j = (s - i + N) % N;
				c[i] = c[j] = i;
			}
			queries.push_back(c);
			queries.push_back(c);
		}
	} else {
		// find spanning tree

		vector<int> dfs_order;
		vector<int> par(N, -1);
		{
			vector<int> vis(N, 0);
			y_combinator([&](auto dfs, int u) -> void {
				dfs_order.push_back(u);
				vis[u] = 1;
				for(int v : adj[u]){
					if(vis[v]) continue;
					par[v] = u;
					dfs(v);
				}
			})(0);
		}
		
		vector<int> rev = dfs_order;
		reverse(rev.begin(), rev.end());
		for(int x : rev){
			vector<int> x_dfs_order;
			vector<int> vis(N, 0);
			vector<int> x_par(N, -1);
			y_combinator([&](auto dfs, int u) -> void {
				x_dfs_order.push_back(u);
				vis[u] = 1;
				for(int v : adj[u]){
					if(vis[v]) continue;
					vector<int> color(N, 0);
					for(int i = 0; i < N; i++) color[i] = i;
					color[u] = color[v] = N;
					queries.push_back(color);
					dfs(v);
					queries.push_back(color);
				}
			})(x);
		}
	}
	cout << queries.size() << '\n';
	for(auto c : queries){
		for(int i = 0; i < N; i++){
			cout << c[i] << " \n"[i == N-1];
		}
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:83:7: warning: unused variable 'is_tree' [-Wunused-variable]
   83 |  bool is_tree = (M == N-1);
      |       ^~~~~~~
# Verdict Execution time Memory 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 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
# Verdict Execution time Memory 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 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 348 KB Output is correct
5 Correct 1 ms 404 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
# Verdict Execution time Memory 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 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 404 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Partially correct 78 ms 14692 KB Partially correct
28 Partially correct 107 ms 14600 KB Partially correct
29 Partially correct 84 ms 14800 KB Partially correct
30 Partially correct 78 ms 14688 KB Partially correct
31 Partially correct 113 ms 14604 KB Partially correct
32 Partially correct 92 ms 14720 KB Partially correct
33 Partially correct 81 ms 14604 KB Partially correct
34 Partially correct 78 ms 14600 KB Partially correct
35 Partially correct 83 ms 14684 KB Partially correct
36 Partially correct 83 ms 14772 KB Partially correct
37 Partially correct 88 ms 14768 KB Partially correct
38 Partially correct 79 ms 14776 KB Partially correct
39 Partially correct 77 ms 14736 KB Partially correct
40 Partially correct 112 ms 14772 KB Partially correct
41 Partially correct 77 ms 14592 KB Partially correct
42 Partially correct 77 ms 14856 KB Partially correct
43 Partially correct 78 ms 14600 KB Partially correct
44 Partially correct 78 ms 14608 KB Partially correct
45 Partially correct 76 ms 14840 KB Partially correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 1 ms 348 KB Output is correct
55 Correct 0 ms 348 KB Output is correct
56 Correct 0 ms 348 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 0 ms 348 KB Output is correct
64 Correct 0 ms 348 KB Output is correct
65 Correct 0 ms 348 KB Output is correct
# Verdict Execution time Memory 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 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 404 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Partially correct 78 ms 14692 KB Partially correct
37 Partially correct 107 ms 14600 KB Partially correct
38 Partially correct 84 ms 14800 KB Partially correct
39 Partially correct 78 ms 14688 KB Partially correct
40 Partially correct 113 ms 14604 KB Partially correct
41 Partially correct 92 ms 14720 KB Partially correct
42 Partially correct 81 ms 14604 KB Partially correct
43 Partially correct 78 ms 14600 KB Partially correct
44 Partially correct 83 ms 14684 KB Partially correct
45 Partially correct 83 ms 14772 KB Partially correct
46 Partially correct 88 ms 14768 KB Partially correct
47 Partially correct 79 ms 14776 KB Partially correct
48 Partially correct 77 ms 14736 KB Partially correct
49 Partially correct 112 ms 14772 KB Partially correct
50 Partially correct 77 ms 14592 KB Partially correct
51 Partially correct 77 ms 14856 KB Partially correct
52 Partially correct 78 ms 14600 KB Partially correct
53 Partially correct 78 ms 14608 KB Partially correct
54 Partially correct 76 ms 14840 KB Partially correct
55 Correct 0 ms 348 KB Output is correct
56 Correct 0 ms 348 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 1 ms 348 KB Output is correct
64 Correct 0 ms 348 KB Output is correct
65 Correct 0 ms 348 KB Output is correct
66 Correct 0 ms 348 KB Output is correct
67 Correct 0 ms 348 KB Output is correct
68 Correct 0 ms 348 KB Output is correct
69 Correct 0 ms 348 KB Output is correct
70 Correct 0 ms 348 KB Output is correct
71 Correct 0 ms 348 KB Output is correct
72 Correct 0 ms 348 KB Output is correct
73 Correct 0 ms 348 KB Output is correct
74 Correct 0 ms 348 KB Output is correct
75 Correct 0 ms 344 KB Output is correct
76 Correct 0 ms 348 KB Output is correct
77 Correct 0 ms 348 KB Output is correct
78 Correct 1 ms 604 KB Output is correct
79 Correct 1 ms 604 KB Output is correct
80 Correct 0 ms 348 KB Output is correct
81 Correct 0 ms 348 KB Output is correct
82 Correct 0 ms 348 KB Output is correct
83 Correct 0 ms 348 KB Output is correct
84 Correct 1 ms 348 KB Output is correct
85 Correct 0 ms 348 KB Output is correct
86 Correct 1 ms 348 KB Output is correct
87 Correct 1 ms 604 KB Output is correct
88 Correct 0 ms 344 KB Output is correct
89 Correct 0 ms 348 KB Output is correct
90 Correct 1 ms 348 KB Output is correct
91 Correct 1 ms 604 KB Output is correct
92 Correct 1 ms 604 KB Output is correct
93 Correct 0 ms 348 KB Output is correct
94 Correct 0 ms 348 KB Output is correct
95 Correct 1 ms 348 KB Output is correct
96 Correct 0 ms 348 KB Output is correct
97 Partially correct 78 ms 14664 KB Partially correct
98 Partially correct 78 ms 14600 KB Partially correct
99 Partially correct 76 ms 14600 KB Partially correct
100 Partially correct 95 ms 14676 KB Partially correct
101 Partially correct 86 ms 14604 KB Partially correct
102 Partially correct 80 ms 14596 KB Partially correct
103 Partially correct 77 ms 14600 KB Partially correct
104 Partially correct 80 ms 14604 KB Partially correct
105 Partially correct 82 ms 14800 KB Partially correct
106 Partially correct 78 ms 14688 KB Partially correct
107 Partially correct 75 ms 14860 KB Partially correct
108 Partially correct 77 ms 14600 KB Partially correct
109 Partially correct 79 ms 14596 KB Partially correct
110 Partially correct 78 ms 14684 KB Partially correct
111 Partially correct 76 ms 14824 KB Partially correct
112 Partially correct 76 ms 14600 KB Partially correct
113 Partially correct 78 ms 14604 KB Partially correct
114 Partially correct 78 ms 14856 KB Partially correct
115 Partially correct 77 ms 14696 KB Partially correct
116 Correct 0 ms 344 KB Output is correct
117 Correct 0 ms 348 KB Output is correct
118 Correct 0 ms 348 KB Output is correct
119 Correct 0 ms 344 KB Output is correct
120 Correct 0 ms 344 KB Output is correct
121 Correct 0 ms 348 KB Output is correct
122 Correct 0 ms 348 KB Output is correct
123 Correct 0 ms 344 KB Output is correct
124 Correct 0 ms 348 KB Output is correct
125 Correct 0 ms 348 KB Output is correct
126 Correct 0 ms 348 KB Output is correct
127 Correct 1 ms 348 KB Output is correct
128 Correct 1 ms 348 KB Output is correct
129 Correct 1 ms 348 KB Output is correct
130 Correct 1 ms 348 KB Output is correct
131 Correct 0 ms 344 KB Output is correct
132 Correct 0 ms 348 KB Output is correct
133 Correct 0 ms 348 KB Output is correct
134 Correct 0 ms 348 KB Output is correct
135 Correct 0 ms 348 KB Output is correct
136 Correct 0 ms 348 KB Output is correct
137 Correct 1 ms 348 KB Output is correct
138 Correct 1 ms 348 KB Output is correct
139 Correct 0 ms 348 KB Output is correct
140 Partially correct 87 ms 14688 KB Partially correct
141 Correct 0 ms 348 KB Output is correct
142 Partially correct 93 ms 14928 KB Partially correct
143 Partially correct 95 ms 14856 KB Partially correct
144 Partially correct 124 ms 14856 KB Partially correct
145 Partially correct 89 ms 14696 KB Partially correct
146 Partially correct 121 ms 14888 KB Partially correct
147 Partially correct 88 ms 14704 KB Partially correct
148 Partially correct 87 ms 14920 KB Partially correct
149 Partially correct 141 ms 14804 KB Partially correct
150 Partially correct 111 ms 14856 KB Partially correct
151 Partially correct 116 ms 14700 KB Partially correct
152 Partially correct 80 ms 14860 KB Partially correct
153 Partially correct 93 ms 14856 KB Partially correct
154 Partially correct 97 ms 14784 KB Partially correct
155 Partially correct 116 ms 14696 KB Partially correct
156 Partially correct 77 ms 14604 KB Partially correct
157 Partially correct 78 ms 14604 KB Partially correct
158 Partially correct 118 ms 14600 KB Partially correct
159 Partially correct 108 ms 14860 KB Partially correct
160 Partially correct 77 ms 14724 KB Partially correct
161 Partially correct 77 ms 14772 KB Partially correct
162 Correct 0 ms 348 KB Output is correct
163 Correct 1 ms 348 KB Output is correct
164 Correct 0 ms 348 KB Output is correct
165 Correct 0 ms 348 KB Output is correct