SRM409 Div2 Hard

1000

やるだけ

view plainprint?

1. const int N = 50 + 1;  
2. vector<int> g[N];  
3.   
4. bool T[N];  
5.   
6. int f(int node)  
7. {  
8.   int cost[node];  
9.   fill(cost, cost + node, 1 << 29);  
10.   cost[0] = 0;  
11.   
12.   queue<int> q;  
13.   
14.   for (int i = 1; i < (int)node; ++i) {  
15.     if (T[i]) {  
16.       q.push(i);  
17.       cost[i] = 0;  
18.     }  
19.   }  
20.   
21.   for (q.push(0); q.size(); q.pop()) {  
22.     int n = q.front();  
23.     each (i, g[n]) {  
24.       if (cost[*i] > cost[n] + 1) {  
25.         cost[*i] = cost[n] + 1;  
26.         q.push(*i);  
27.       }  
28.     }  
29.   }  
30.   
31.   return *max_element(cost, cost + node);  
32. }  
33.   
34. int rec(int i, int tc, int node)  
35. {  
36.   if (tc == 0) return f(node);  
37.   int mn = 1 << 28;  
38.   for (; i < node; ++i) {  
39.     T[i] = true;  
40.     mn = min(mn, rec(i + 1, tc - 1, node));  
41.     T[i] = false;  
42.   }  
43.   return mn;  
44. }  
45.   
46. class TeleportsNetwork {  
47. public:  
48.   int distribute(int tc, vector <int> X, vector <int> Y)  
49.   {  
50.     fill(T, T + N, false);  
51.     fill(g, g + N, vector<int>());  
52.   
53.     const int node = X.size();  
54.   
55.     double d[node][node];  
56.   
57.     for (int i = 0; i < (int)node; ++i) {  
58.       for (int j = 0; j < (int)node; ++j) {  
59.         double x = X[i] - X[j];  
60.         double y = Y[i] - Y[j];  
61.         d[i][j] = sqrt(x * x + y * y);  
62.       }  
63.     }  
64.   
65.     for (int i = 1; i < (int)node; ++i) {  
66.       double dist = 1e126;  
67.       int idx;  
68.       for (int j = 0; j < (int)node; ++j) {  
69.         if (d[0][i] < d[0][j]) continue;  
70.         if (i == j) continue;  
71.         if (d[i][j] < dist) {  
72.           dist = d[i][j];  
73.           idx = j;  
74.         }  
75.         if (dist == d[i][j]) {  
76.           if (X[j] < X[idx]) idx = j;  
77.           if (X[j] == X[idx] && Y[j] < Y[idx]) idx = j;  
78.         }  
79.       }  
80.       g[i].push_back(idx);  
81.       g[idx].push_back(i);  
82.     }  
83.   
84.     return rec(1, tc, node);  
85.   }  
86. };  

const int N = 50 + 1;
vector<int> g[N];

bool T[N];

int f(int node)
{
  int cost[node];
  fill(cost, cost + node, 1 << 29);
  cost[0] = 0;

  queue<int> q;

  for (int i = 1; i < (int)node; ++i) {
    if (T[i]) {
      q.push(i);
      cost[i] = 0;
    }
  }

  for (q.push(0); q.size(); q.pop()) {
    int n = q.front();
    each (i, g[n]) {
      if (cost[*i] > cost[n] + 1) {
        cost[*i] = cost[n] + 1;
        q.push(*i);
      }
    }
  }

  return *max_element(cost, cost + node);
}

int rec(int i, int tc, int node)
{
  if (tc == 0) return f(node);
  int mn = 1 << 28;
  for (; i < node; ++i) {
    T[i] = true;
    mn = min(mn, rec(i + 1, tc - 1, node));
    T[i] = false;
  }
  return mn;
}

class TeleportsNetwork {
public:
  int distribute(int tc, vector <int> X, vector <int> Y)
  {
    fill(T, T + N, false);
    fill(g, g + N, vector<int>());

    const int node = X.size();

    double d[node][node];

    for (int i = 0; i < (int)node; ++i) {
      for (int j = 0; j < (int)node; ++j) {
        double x = X[i] - X[j];
        double y = Y[i] - Y[j];
        d[i][j] = sqrt(x * x + y * y);
      }
    }

    for (int i = 1; i < (int)node; ++i) {
      double dist = 1e126;
      int idx;
      for (int j = 0; j < (int)node; ++j) {
        if (d[0][i] < d[0][j]) continue;
        if (i == j) continue;
        if (d[i][j] < dist) {
          dist = d[i][j];
          idx = j;
        }
        if (dist == d[i][j]) {
          if (X[j] < X[idx]) idx = j;
          if (X[j] == X[idx] && Y[j] < Y[idx]) idx = j;
        }
      }
      g[i].push_back(idx);
      g[idx].push_back(i);
    }

    return rec(1, tc, node);
  }
};