Submission #1355127
Source Code Expand
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
using namespace std;
#ifndef _DEBUG
#define main_ main
#endif
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<string> vs;
template <typename T>
using keyVal = pair<string, T>;
template<typename T>
bool val_greater(const keyVal<T>& left, const keyVal<T>& right) {
return left.second > right.second;
}
vs split(string str, char sep) {
vs v; stringstream ss(str); string t;
while (getline(ss, t, sep)) v.push_back(t);
return v;
}
void init_global() {}
int N, X;
vi h;
vvi E;
vb visited;
void sub_dfs(int s, bool& found) {
if (s > N - 1) return;
if (h[s] == 1) {
found = true;
return;
}
FOR(t, 0, N) {
if (E[s][t] == 0 || visited[t]) continue;
sub_dfs(t, found);
if (found) break;
}
}
void dfs(int s, int& len) {
if (s > N - 1) return;
visited[s] = true;
FOR(t, 0, N) {
if (E[s][t] == 0 || visited[t]) continue;
bool found = false;
sub_dfs(t, found);
if (!found) continue;
len++;
dfs(t, len);
len++;
}
}
int main_() {
cin.tie(0);
ios::sync_with_stdio(false);
#ifndef _DEBUG
init_global();
#endif
cin >> N >> X;
X--;
h.resize(N);
FOR(i, 0, N) cin >> h[i];
vi A(N - 1), B(N - 1);
FOR(i, 0, N - 1) {
cin >> A[i] >> B[i];
A[i]--; B[i]--;
}
E.resize(N, vi(N, 0));
FOR(i, 0, N - 1) {
E[A[i]][B[i]] = E[B[i]][A[i]] = 1;
}
int len = 0;
visited.resize(N, false);
dfs(X, len);
int ans = len;
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - ツリーグラフ |
User |
apprec |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1946 Byte |
Status |
RE |
Exec Time |
645 ms |
Memory |
262400 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
Status |
|
|
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 |
RE |
243 ms |
262400 KB |
subtask1_line03.txt |
RE |
245 ms |
262400 KB |
subtask1_line04.txt |
AC |
1 ms |
256 KB |
subtask1_line05.txt |
AC |
1 ms |
256 KB |
subtask1_line06.txt |
RE |
236 ms |
262400 KB |
subtask1_random01.txt |
RE |
562 ms |
262400 KB |
subtask1_random02.txt |
RE |
425 ms |
262400 KB |
subtask1_random03.txt |
RE |
277 ms |
262400 KB |
subtask1_random04.txt |
RE |
373 ms |
262400 KB |
subtask1_random05.txt |
RE |
645 ms |
262400 KB |
subtask1_random06.txt |
RE |
502 ms |
262400 KB |
subtask1_random07.txt |
RE |
546 ms |
262400 KB |
subtask1_random08.txt |
RE |
420 ms |
262400 KB |
subtask1_special01.txt |
AC |
1 ms |
256 KB |
subtask1_special02.txt |
AC |
1 ms |
256 KB |
subtask1_special03.txt |
AC |
1 ms |
256 KB |
subtask1_special04.txt |
AC |
1 ms |
256 KB |