oj.uz

답안 #640578

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
640578 2022-09-15T01:28:52 Z Tuanlinh123 Paprike (COI18_paprike) C++17
13 / 100
 39 ms 12916 KB 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

#define LOCALIO "C:/Users/admin/Documents/Code/freopen/"

vector <ll> A[100005];
ll a[100005], ans, n, k, num;
bool used[100005];

void dfs(ll s)
{
    used[s]=1;
    for (ll i=0; i<A[s].size(); i++)
    {
        ll v=A[s][i];
        if (used[v])
            continue;
        if (a[v]+num<=k)
        {
            num+=a[v];
            dfs(v);
        }
    }
    for (ll i=0; i<A[s].size(); i++)
    {
        ll v=A[s][i];
        if (used[v])
            continue;
        num=a[v];
        ans++;
        dfs(v);
    }
}


int main()
{
    #ifdef LOCAL
        freopen( LOCALIO "input.txt","r",stdin) ;
        freopen( LOCALIO "output.txt","w",stdout) ;
    #endif

    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
//	freopen("FIBONACCI.inp","r",stdin);
//	freopen("FIBONACCI.out","w",stdout);
    cin >> n >> k;
    for (ll i=1; i<=n; i++)
        cin >> a[i];
    for (ll i=1; i<n; i++)
    {
        ll x, y; cin >> x >> y;
        A[x].pb(y); A[y].pb(x);
    }
    num=a[1];
    dfs(1);
    cout << ans;
}

Compilation message

paprike.cpp: In function 'void dfs(long long int)':
paprike.cpp:21:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (ll i=0; i<A[s].size(); i++)
      |                  ~^~~~~~~~~~~~
paprike.cpp:32:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (ll i=0; i<A[s].size(); i++)
      |                  ~^~~~~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 12876 KB Output is correct
2 Correct 39 ms 12872 KB Output is correct
3 Correct 36 ms 12908 KB Output is correct
4 Correct 35 ms 12836 KB Output is correct
5 Correct 34 ms 12876 KB Output is correct
6 Correct 36 ms 12916 KB Output is correct
7 Correct 34 ms 12876 KB Output is correct
8 Correct 32 ms 12808 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -