Submission #47231

#	Time	Username	Problem	Language	Result	Execution time	Memory
47231		robert	Mousetrap (CEOI17_mousetrap)	C++14	0 / 100	2 ms	356 KiB

mousetrap

#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 (stderr)

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
• Subtask 2: 0 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35