oj.uz

Submission #47231

# Submission time Handle Problem Language Result Execution time Memory
47231 2018-04-29T10:47:46 Z robert Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 2 ms 356 KB 
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

vector<vii> g;

int N, T, M;
int m[30][(1<<12)][(1<<12)];

int solve(int c, int w, int d);

int mouse(int c, int w, int d){
	int ret = 0;
	for(int x=0; x<g[c].size(); x++){
		if(!((1<<g[c][x].second)&w)&&!((1<<g[c][x].second)&d))
			ret = max(ret, solve(g[c][x].first, w, d));
	}
	if(ret==0)
		ret = solve(c, w, d);
	return ret;
}

int solve(int c, int w, int d){
	cout << c << endl;
	if(c==T)
		return 0;
	if(m[c][w][d]!=-1&&m[c][w][d]!=-2)
		return m[c][w][d];
	int ret = 1e9;
	if(m[c][w][d]!=-2){
		m[c][w][d] = -2;
		ret = mouse(c, w, d);
	} else {
		return -1;
	}
	for(int x=1; x<N; x++){
		cout << x << endl;
		if(d&(1<<x)){
			ret = min(ret, mouse(c, w, d-(1<<x)));
		}
		ret = min(ret, mouse(c, w|(1<<x), d));
	}
	return m[c][w][d] = ret;
}

int main(){
	cin>>N>>T>>M;
	g.assign(N+1, vii());
	int A, B;
	for(int n=1; n<N; n++){
		cin>>A>>B;
		g[A].push_back({B, n});
		g[B].push_back({A, n});
	}
	memset(m, -1, sizeof(m));
	cout << solve(M, 0, 0) << endl;
	return 0;
}

Compilation message

mousetrap.cpp: In function 'int mouse(int, int, int)':
mousetrap.cpp:20:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int x=0; x<g[c].size(); x++){
               ~^~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -