SRM670 div.1 450/div.2 1050 Treestrat.cpp

Treestrat.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

int D[64][64];
const int INF = 1<<20;

class Treestrat {
public:
  int roundcnt(vector<int> tree, vector<int> A, vector<int> B) {
    int N = tree.size() + 1;
    
    REP(i, N) REP(j, N) D[i][j] = INF;
    REP(i, N) D[i][i] = 0;
    REP(i, N-1) D[i+1][tree[i]] = D[tree[i]][i+1] = 1;
    // Warshall-Floyd
    REP(k, N) REP(i, N) REP(j, N)
      D[i][j] = min(D[i][j], D[i][k] + D[k][j]);

    int ans = INF;
    for (int a : A) {
      int max_Ai = 0;
      REP(last, N) {
	int min_Bj = INF;
	bool is_valid = true;
	for (int b : B) {
	  if (D[a][last] >= D[b][last]) {
	    is_valid = false; // このlastはダメ
	    break;
	  } else if (D[b][last] < min_Bj) {
	    min_Bj = D[b][last];
	  }
	}
	if (!is_valid) {
	  continue;
	} else {
	  assert(min_Bj != INF);
	  max_Ai = max(max_Ai, min_Bj);
	}
      }
      assert(max_Ai != 0);
      ans = min(ans, max_Ai);
    }
    return ans;
  }
};