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
Task B - ツリーグラフ
User nida_001
Language C++11 (GCC 4.8.1)
Score 0
Code Size 2162 Byte
Status WA
Exec Time 27 ms
Memory 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
Sample subtask0_sample_01.txt, subtask0_sample_02.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_line01.txt, subtask1_line02.txt, subtask1_line03.txt, subtask1_line04.txt, subtask1_line05.txt, subtask1_line06.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_random06.txt, subtask1_random07.txt, subtask1_random08.txt, subtask1_special01.txt, subtask1_special02.txt, subtask1_special03.txt, subtask1_special04.txt
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