Submission #1048476

# Submission time Handle Problem Language Result Execution time Memory
1048476 2024-08-08T07:50:03 Z ksun69(#11093) Make them Meet (EGOI24_makethemmeet) C++17
58.3864 / 100
75 ms 7820 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());
		vector<int> active(N, 1);
		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] || !active[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);
			active[x] = 0;
		}
	}
	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 1 ms 344 KB Output is correct
3 Correct 0 ms 412 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 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 1 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 2 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 604 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 1 ms 344 KB Output is correct
3 Correct 0 ms 412 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 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 604 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 0 ms 348 KB Output is correct
16 Correct 1 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 352 KB Output is correct
21 Correct 2 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 43 ms 7564 KB Partially correct
28 Partially correct 43 ms 7484 KB Partially correct
29 Partially correct 43 ms 7568 KB Partially correct
30 Partially correct 57 ms 7524 KB Partially correct
31 Partially correct 43 ms 7648 KB Partially correct
32 Partially correct 44 ms 7504 KB Partially correct
33 Partially correct 39 ms 7564 KB Partially correct
34 Partially correct 42 ms 7576 KB Partially correct
35 Partially correct 38 ms 7568 KB Partially correct
36 Partially correct 38 ms 7440 KB Partially correct
37 Partially correct 38 ms 7564 KB Partially correct
38 Partially correct 75 ms 7564 KB Partially correct
39 Partially correct 49 ms 7672 KB Partially correct
40 Partially correct 39 ms 7564 KB Partially correct
41 Partially correct 39 ms 7508 KB Partially correct
42 Partially correct 40 ms 7632 KB Partially correct
43 Partially correct 43 ms 7532 KB Partially correct
44 Partially correct 39 ms 7564 KB Partially correct
45 Partially correct 45 ms 7420 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 0 ms 348 KB Output is correct
55 Correct 0 ms 344 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 456 KB Output is correct
59 Correct 1 ms 344 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 1 ms 512 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 1 ms 344 KB Output is correct
3 Correct 0 ms 412 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 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 1 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 2 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 604 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 0 ms 348 KB Output is correct
25 Correct 1 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 352 KB Output is correct
30 Correct 2 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 43 ms 7564 KB Partially correct
37 Partially correct 43 ms 7484 KB Partially correct
38 Partially correct 43 ms 7568 KB Partially correct
39 Partially correct 57 ms 7524 KB Partially correct
40 Partially correct 43 ms 7648 KB Partially correct
41 Partially correct 44 ms 7504 KB Partially correct
42 Partially correct 39 ms 7564 KB Partially correct
43 Partially correct 42 ms 7576 KB Partially correct
44 Partially correct 38 ms 7568 KB Partially correct
45 Partially correct 38 ms 7440 KB Partially correct
46 Partially correct 38 ms 7564 KB Partially correct
47 Partially correct 75 ms 7564 KB Partially correct
48 Partially correct 49 ms 7672 KB Partially correct
49 Partially correct 39 ms 7564 KB Partially correct
50 Partially correct 39 ms 7508 KB Partially correct
51 Partially correct 40 ms 7632 KB Partially correct
52 Partially correct 43 ms 7532 KB Partially correct
53 Partially correct 39 ms 7564 KB Partially correct
54 Partially correct 45 ms 7420 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 0 ms 348 KB Output is correct
64 Correct 0 ms 344 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 456 KB Output is correct
68 Correct 1 ms 344 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 1 ms 348 KB Output is correct
73 Correct 1 ms 512 KB Output is correct
74 Correct 0 ms 348 KB Output is correct
75 Correct 0 ms 348 KB Output is correct
76 Correct 0 ms 348 KB Output is correct
77 Correct 1 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 344 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 0 ms 344 KB Output is correct
85 Correct 0 ms 348 KB Output is correct
86 Correct 1 ms 348 KB Output is correct
87 Correct 3 ms 604 KB Output is correct
88 Correct 0 ms 348 KB Output is correct
89 Correct 0 ms 348 KB Output is correct
90 Correct 1 ms 344 KB Output is correct
91 Correct 2 ms 604 KB Output is correct
92 Correct 1 ms 604 KB Output is correct
93 Correct 1 ms 348 KB Output is correct
94 Correct 0 ms 348 KB Output is correct
95 Correct 0 ms 348 KB Output is correct
96 Correct 0 ms 348 KB Output is correct
97 Partially correct 40 ms 7568 KB Partially correct
98 Partially correct 41 ms 7672 KB Partially correct
99 Partially correct 44 ms 7564 KB Partially correct
100 Partially correct 39 ms 7664 KB Partially correct
101 Partially correct 43 ms 7456 KB Partially correct
102 Partially correct 40 ms 7820 KB Partially correct
103 Partially correct 40 ms 7536 KB Partially correct
104 Partially correct 38 ms 7564 KB Partially correct
105 Partially correct 39 ms 7568 KB Partially correct
106 Partially correct 38 ms 7568 KB Partially correct
107 Partially correct 40 ms 7680 KB Partially correct
108 Partially correct 38 ms 7560 KB Partially correct
109 Partially correct 44 ms 7564 KB Partially correct
110 Partially correct 38 ms 7564 KB Partially correct
111 Partially correct 38 ms 7576 KB Partially correct
112 Partially correct 40 ms 7564 KB Partially correct
113 Partially correct 38 ms 7560 KB Partially correct
114 Partially correct 38 ms 7564 KB Partially correct
115 Partially correct 38 ms 7564 KB Partially correct
116 Correct 0 ms 348 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 348 KB Output is correct
120 Correct 0 ms 348 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 348 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 0 ms 348 KB Output is correct
128 Correct 0 ms 348 KB Output is correct
129 Correct 0 ms 348 KB Output is correct
130 Correct 0 ms 348 KB Output is correct
131 Correct 0 ms 348 KB Output is correct
132 Correct 0 ms 600 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 0 ms 348 KB Output is correct
138 Correct 0 ms 348 KB Output is correct
139 Correct 0 ms 348 KB Output is correct
140 Partially correct 40 ms 7564 KB Partially correct
141 Correct 0 ms 348 KB Output is correct
142 Partially correct 39 ms 7608 KB Partially correct
143 Partially correct 40 ms 7568 KB Partially correct
144 Partially correct 39 ms 7576 KB Partially correct
145 Partially correct 40 ms 7696 KB Partially correct
146 Partially correct 38 ms 7568 KB Partially correct
147 Partially correct 40 ms 7564 KB Partially correct
148 Partially correct 38 ms 7560 KB Partially correct
149 Partially correct 40 ms 7564 KB Partially correct
150 Partially correct 39 ms 7568 KB Partially correct
151 Partially correct 38 ms 7564 KB Partially correct
152 Partially correct 38 ms 7564 KB Partially correct
153 Partially correct 38 ms 7564 KB Partially correct
154 Partially correct 38 ms 7564 KB Partially correct
155 Partially correct 38 ms 7568 KB Partially correct
156 Partially correct 38 ms 7568 KB Partially correct
157 Partially correct 38 ms 7576 KB Partially correct
158 Partially correct 43 ms 7564 KB Partially correct
159 Partially correct 39 ms 7704 KB Partially correct
160 Partially correct 39 ms 7456 KB Partially correct
161 Partially correct 40 ms 7448 KB Partially correct
162 Correct 1 ms 348 KB Output is correct
163 Correct 0 ms 348 KB Output is correct
164 Correct 0 ms 348 KB Output is correct
165 Correct 1 ms 344 KB Output is correct