oj.uz

Submission #1048472

# Submission time Handle Problem Language Result Execution time Memory
1048472 2024-08-08T07:49:51 Z 김은성(#11035) Make them Meet (EGOI24_makethemmeet) C++17
7.01198 / 100
 99 ms 14852 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> graph[109];
vector<vector<int> > moves;
vector<vector<int> > st;
int n, color[109];
void reset(){
	for(int i=0; i<n; i++)
		color[i] = i+1;
}
void make_move(){
	vector<int> temp;
	for(int i=0; i<n; i++)
		temp.push_back(color[i]);
	moves.push_back(temp);
	st.push_back(temp);
}
void go_back(){
	while(!st.empty()){
		moves.push_back(st.back());
		st.pop_back();
	}
}
void answer(){
	assert(moves.size() <= 20000);
	printf("%d\n", moves.size());
	for(vector<int> u: moves){
		for(int v: u)
			printf("%d ", v);
		printf("\n");
	}
}
vector<int> tree[109], child[109];
bool ch[109];
int par[109];
void dfs_span(int v){
	ch[v] = 1;
	for(int u: graph[v]){
		if(!ch[u]){
			tree[v].push_back(u);
			tree[u].push_back(v);
			child[v].push_back(u);
			dfs_span(u);
			par[u] = v;
		}
	}
}
void dfs(int v){
	ch[v] = 1;
	for(int u: tree[v]){
		if(!ch[u]){
			reset();
			color[v] = color[u] = v+1;
			make_move();
			dfs(u);
			go_back();
		}
	}
}
int main(){
	int m, i, j, k, u, v;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	dfs_span(0);
	for(i=0; i<n; i++){
		memset(ch, 0, sizeof(ch));
		dfs(i);
	}
	answer();
	return 0;
}

/*

	for(i=1; i<n; i++){
		for(k=0; k<n; k++){
			color[k]= k+1;
		}
		bool ch[109] = {0, };
		vector<int> vec;
		for(j=0; j<n; j++){
			if(!ch[j]){
				for(int j2 = j; !ch[j2]; j2 = (j2 + i) % n){
					//printf("j2=%d\n", j2);
					vec.push_back(j2);
					ch[j2]= 1;
				}
			}
		}
		for(k=0; k<n; k++){
			color[k]= k+1;
		}
		for(j=0; j<vec.size()-1; j+=2){
			color[vec[j]] = color[(vec[j] + i) % n] = vec[j]+1;
		}
		make_move();
		make_move();
		for(k=0; k<n; k++){
			color[k]= k+1;
		}
		for(j=1; j<vec.size()-1; j+=2){
			color[vec[j]] = color[(vec[j] + i) % n] = vec[j]+1;
		}
		make_move();
		make_move();
		for(k=0; k<n; k++){
			color[k]= k+1;
		}
		for(j=vec.size()-1; j<=vec.size()-1; j+=2){
			color[vec[j]] = color[(vec[j] + i) % n] = vec[j]+1;

		}
		make_move();
		make_move();
	}
	answer();
	return 0;
*/

Compilation message

Main.cpp: In function 'void answer()':
Main.cpp:26:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wformat=]
   26 |  printf("%d\n", moves.size());
      |          ~^     ~~~~~~~~~~~~
      |           |               |
      |           int             std::vector<std::vector<int> >::size_type {aka long unsigned int}
      |          %ld
Main.cpp: In function 'int main()':
Main.cpp:61:12: warning: unused variable 'j' [-Wunused-variable]
   61 |  int m, i, j, k, u, v;
      |            ^
Main.cpp:61:15: warning: unused variable 'k' [-Wunused-variable]
   61 |  int m, i, j, k, u, v;
      |               ^
Main.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB If people start at 2 and 3, then they can avoid each other
4 Halted 0 ms 0 KB -

Subtask #2
3.7981566818 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 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 348 KB Output is correct
6 Partially correct 3 ms 604 KB Partially correct
7 Partially correct 6 ms 1368 KB Partially correct
8 Partially correct 21 ms 2100 KB Partially correct
9 Partially correct 88 ms 14852 KB Partially correct

Subtask #3
3.2138248846 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Partially correct 23 ms 2040 KB Partially correct
5 Partially correct 99 ms 14204 KB Partially correct
6 Partially correct 97 ms 14736 KB Partially correct
7 Partially correct 32 ms 4236 KB Partially 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 348 KB Output is correct
3 Incorrect 0 ms 348 KB If people start at 2 and 3, then they can avoid each other
4 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 348 KB Output is correct
3 Incorrect 0 ms 348 KB If people start at 2 and 3, then they can avoid each other
4 Halted 0 ms 0 KB -