Submission #1725578


Source Code Expand

#include<bits/stdc++.h>

using namespace std;

int n,x;
bool duel[101];
int d[102][102];
int dx;
int d_c;
const int INF = 10000;
int main() {
  cin >> n >> x;

  for(int i = 1; i <= n; i++) {
    int h;
    cin >> h;
    if(h) {
      d_c++;
      duel[i] = true;
    }
  }

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

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

  dx = x;

  int ans = 0;
  int dd;
  
  for(int i = 0; i < d_c; i++) {
    int tmp = 1000;
    for(int i = 1; i <= n; i++) {
      if(!duel[i])continue;
      if(tmp > d[dx][i]) {
	//	cout << "d["<<dx<<"]["<<i<<"] = "<<d[dx][i]<<endl;
	tmp = d[dx][i];
	dd = i;
      }
    }
    dx = dd;
    duel[dd] = false;
    ans += tmp;
  }
  cout << ans + d[dx][x] << endl;
}
    
  

Submission Info

Submission Time
Task B - ツリーグラフ
User shossie1016
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1079 Byte
Status WA
Exec Time 3 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 14
WA × 6
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 1 ms 256 KB
subtask0_sample_02.txt AC 1 ms 256 KB
subtask1_line01.txt AC 1 ms 256 KB
subtask1_line02.txt AC 3 ms 256 KB
subtask1_line03.txt AC 1 ms 256 KB
subtask1_line04.txt AC 3 ms 256 KB
subtask1_line05.txt AC 3 ms 256 KB
subtask1_line06.txt AC 3 ms 256 KB
subtask1_random01.txt WA 3 ms 256 KB
subtask1_random02.txt AC 1 ms 256 KB
subtask1_random03.txt WA 1 ms 256 KB
subtask1_random04.txt AC 2 ms 256 KB
subtask1_random05.txt WA 3 ms 256 KB
subtask1_random06.txt WA 3 ms 256 KB
subtask1_random07.txt WA 3 ms 256 KB
subtask1_random08.txt WA 3 ms 256 KB
subtask1_special01.txt AC 1 ms 256 KB
subtask1_special02.txt AC 3 ms 256 KB
subtask1_special03.txt AC 3 ms 256 KB
subtask1_special04.txt AC 2 ms 256 KB