Submission #286823
Source Code Expand
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <stack>
#include <climits>
#include <deque>
#include <bitset>
#include <cassert>
#include <ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
// adjust problem by problem
const double EPS=1e-8;
const double PI=acos(-1.0);
// rep macro
#define REP(i,x,n) for(int i=x;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define RREP(i,x,n) for(int i=x;i>=(int)(n);--i)
#define rrep(i,n) RREP(i,n,0)
#ifdef __GNUC__
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
int popcount(int n){return __builtin_popcount(n);}
int popcount(ll n){return __builtin_popcountll(n);}
#endif
#ifndef __GNUC__
int popcount(unsigned int n){int cnt=0;for(int i=0;i<32;i++)if((n>>i)&1)cnt++;return cnt;}
int popcountll(unsigned ll n){int cnt=0;for(int i=0;i<64;i++)if((n>>i)&1)cnt++;return cnt;}
#endif
template<class T>int SIZE(T a){return a.size();}
template<class T>string IntToString(T num){string res;stringstream ss;ss<<num;return ss.str();}
template<class T>T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template<class T>T lcm(T a,T b){return a/gcd(a,b)*b;}
ll getTen(int a){return (a<=0)?1:(getTen(a-1)*10);}
bool EQ(double a,double b){return abs(a-b)<EPS;}
void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}
vector<string> split(string str,char del){
vector<string> res;
for(int i=0,s=0;i<SIZE(str);i++){
if(str[i]==del){if(i-s!=0)res.push_back(str.substr(s,i-s));s=i+1;}
else if(i==SIZE(str)-1){res.push_back(str.substr(s));}
}
return res;
}
struct TimeWatch{
clock_t start_,end_;
void start(){start_=clock();}
double stop(){return (double)(clock()-start_)/CLOCKS_PER_SEC;}
};
int N,X;
int H[101];
int A[101];
int B[101];
int sums[101];
vector<int>G[101];
int dfs(int pos,int par){
int cnt = H[pos];
for(int to : G[pos]){
if(to == par)continue;
cnt += dfs(to, pos);
}
//cout<<pos<<" "<<cnt<<endl;
sums[pos] = cnt;
return cnt;
}
int dfs2(int pos,int par){
int res=0;
for(int to : G[pos]){
if(to == par)continue;
if(sums[to]>0){
res+=(dfs2(to, pos)+1);
}
}
return res+1;
}
int main(){
cin>>N>>X;
X--;
for(int i=0;i<N;i++)cin>>H[i];
for(int i=0;i<N-1;i++){
cin>>A[i]>>B[i];
A[i]--;B[i]--;
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
dfs(X, -1);
cout<<dfs2(X, -1)-1<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - ツリーグラフ |
User |
ishikado |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
2757 Byte |
Status |
AC |
Exec Time |
39 ms |
Memory |
932 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 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 |
21 ms |
924 KB |
subtask0_sample_02.txt |
AC |
21 ms |
924 KB |
subtask1_line01.txt |
AC |
22 ms |
924 KB |
subtask1_line02.txt |
AC |
22 ms |
796 KB |
subtask1_line03.txt |
AC |
23 ms |
800 KB |
subtask1_line04.txt |
AC |
24 ms |
796 KB |
subtask1_line05.txt |
AC |
31 ms |
700 KB |
subtask1_line06.txt |
AC |
39 ms |
768 KB |
subtask1_random01.txt |
AC |
23 ms |
928 KB |
subtask1_random02.txt |
AC |
23 ms |
800 KB |
subtask1_random03.txt |
AC |
23 ms |
924 KB |
subtask1_random04.txt |
AC |
22 ms |
932 KB |
subtask1_random05.txt |
AC |
21 ms |
792 KB |
subtask1_random06.txt |
AC |
22 ms |
924 KB |
subtask1_random07.txt |
AC |
23 ms |
932 KB |
subtask1_random08.txt |
AC |
22 ms |
800 KB |
subtask1_special01.txt |
AC |
20 ms |
920 KB |
subtask1_special02.txt |
AC |
23 ms |
800 KB |
subtask1_special03.txt |
AC |
22 ms |
920 KB |
subtask1_special04.txt |
AC |
22 ms |
800 KB |