Contest Duration: - (local time) (90 minutes) Back to Home

Submission #286984

Source Code Expand

Copy
```#include <iostream>
#include <stdio.h>
#include <istream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <complex>
#include <iomanip>

using namespace std;

typedef long long int ll;

int main(int argc, const char * argv[])
{
int _n, _x;
cin >> _n >> _x;
const int n = _n;
const int x = _x - 1;

const int MAX_N = 100;
bool h[MAX_N];

int hcount = 0;
for (int i = 0; i < n; i++) {
int b;
cin >> b;
h[i] = (b == 1);
if (b == 1) { hcount++; };
}

int dist[MAX_N][MAX_N];

for (int i = 0; i < MAX_N; i++) {
for (int j = 0; j < MAX_N; j++) {
dist[i][j] = 100000;
if (i == j) {
dist[i][j] = 0;
}
}
}

for (int i = 0; i < n-1; i++) {
int a, b;
cin >> a >> b;
a--; b--;
dist[a][b] = dist[b][a] = 1;
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}

#if 0
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << dist[i][j] << " ";
}
cout << endl;
}
cout << endl;
#endif

int cost = 0;
int pos = x;
for (int RR = 0; RR < hcount; RR++) {
int min = 1000000;
int hi = 0;

#if 0
cout << "pos=" << pos << endl;
#endif
for (int i = 0; i < n; i++) {
if (h[i] && min > dist[pos][i]) {
min = dist[pos][i];
hi = i;
}
}
cost += min;
h[hi] = false;
pos = hi;
}

cost += dist[pos][x];

cout << cost << endl;

// vector<vector<int>> tree(n, vector<int>(0));

}

```

#### Submission Info

Submission Time 2014-11-29 21:34:40+0900 B - ツリーグラフ nida_001 C++11 (GCC 4.8.1) 0 2162 Byte WA 27 ms 928 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
 AC × 2
 AC × 12 WA × 8
Set Name Test Cases
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 23 ms 924 KB
subtask0_sample_02.txt AC 22 ms 928 KB
subtask1_line01.txt AC 23 ms 928 KB
subtask1_line02.txt AC 23 ms 920 KB
subtask1_line03.txt AC 23 ms 796 KB
subtask1_line04.txt AC 26 ms 800 KB
subtask1_line05.txt AC 24 ms 928 KB
subtask1_line06.txt AC 24 ms 920 KB
subtask1_random01.txt WA 26 ms 804 KB
subtask1_random02.txt WA 23 ms 800 KB
subtask1_random03.txt WA 25 ms 920 KB
subtask1_random04.txt WA 24 ms 796 KB
subtask1_random05.txt WA 24 ms 920 KB
subtask1_random06.txt WA 25 ms 736 KB
subtask1_random07.txt WA 25 ms 808 KB
subtask1_random08.txt WA 24 ms 804 KB
subtask1_special01.txt AC 21 ms 924 KB
subtask1_special02.txt AC 27 ms 928 KB
subtask1_special03.txt AC 26 ms 912 KB
subtask1_special04.txt AC 23 ms 800 KB