SRM583 Div1

1331->1501 初めての黄色！Med通せて嬉しみ。(遅いけど)

Easy TravelOnMars
環状な路線での最短距離問題。bfsやるだけ modを取って負の値になることがあるので落ちまくっていたらしい

int n;
int d[60];

class TravelOnMars{
    public:
	int minTimes(vector <int> range, int s, int g){
	    n = range.size();
	    fill(d, d + n, 110);
	    d[s] = 0;
	    queue<int> q;
	    q.push(s);
	    while(!q.empty()){
		int v = q.front(); q.pop();
		if(v == g) break;
		for(int i = v - range[v]; i <= v + range[v]; ++i){
		    int now = i % n;
		    if(now < 0) now += n;
		    if(d[now] == 110){
			d[now] = d[v] + 1;
			q.push(now);
		    }
		}
	    }
	    return d[g];
	}
}

Medium TurnOnLamps
木の上で2点を選んで間にある道のスイッチを切り替えるという操作を最小何回で目的の状態にできるか。

greedyやるだけ。デバッグ力低かった

int n, ans;
vector<P> g[60];
int ch[60];

int calc(int v, int p){
    int ret = 0;
    rep(i, g[v].size()) if(g[v][i].fi != p){
	int tmp = calc(g[v][i].fi, v);
	if(~ch[g[v][i].se] && ((tmp & 1) != ch[g[v][i].se])){
	    if(tmp == 1) ++ans;
	    tmp = ch[g[v][i].se];
	}
	//if(v == 0) printf("%d\n", tmp);
	ret += tmp;
    }
    ans += ret / 2;
    ret &= 1;
    //printf("vertex:%d, return:%d, ans:%d\n", v, ret, ans);
    return ret;
}

class TurnOnLamps{
    public:
	int minimize(vector <int> roads, string initState, string isImportant){
	    memset(ch, false, sizeof(false)); 
	    rep(i, 60) g[i].clear(); 
	    ans = 0;
	    n = (int)roads.size() + 1;

	    rep(i, n - 1){
		g[i + 1].pb(mp(roads[i], i));
		g[roads[i]].pb(mp(i + 1, i));
	    }
	    rep(i, n - 1){
		if(isImportant[i] == '0') ch[i] = -1;
		else if(initState[i] == '1') ch[i] = 0;
		else ch[i] = 1;
	    }
	    if(calc(0, -1) & 1) ++ans;
	    return ans;
	}
};