oj.uz

Submission #1048468

# Submission time Handle Problem Language Result Execution time Memory
1048468 2024-08-08T07:49:16 Z ksun69(#11093) Make them Meet (EGOI24_makethemmeet) C++17
34 / 100
 2 ms 616 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] = x;
					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);
      |       ^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct

Subtask #2
13.0 / 13.0

# 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 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 2 ms 604 KB Output is correct

Subtask #3
11.0 / 11.0

# 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 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

Subtask #4
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 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 1 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 616 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 1 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 Incorrect 0 ms 348 KB If people start at 0 and 1, then they can avoid each other
25 Halted 0 ms 0 KB -

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 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 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 2 ms 604 KB Output is correct
15 Correct 0 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 1 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 616 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 1 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 Incorrect 0 ms 348 KB If people start at 0 and 1, then they can avoid each other
34 Halted 0 ms 0 KB -