oj.uz

Submission #502753

# Submission time Handle Problem Language Result Execution time Memory
502753 2022-01-06T14:31:00 Z ctd6969 Džumbus (COCI19_dzumbus) C++17
0 / 110
 28 ms 2892 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double db;

const ll mod = 1e9 + 7; // 998244353
const ll inf = 1e18;

using pl = pair<ll,ll>;
using pi = pair<int,int>;
using vi = vector<int>; 
using vl = vector<ll>; 
using vpi = vector<pair<int,int>>;
using vpl = vector<pair<ll,ll>>;


#define mp make_pair
#define f first
#define s second

#define foru(i,a,b) for(ll i = a ; i <= b;i++)
#define ford(i,a,b) for(ll i = a ; i >= b;i--)

#define psh push
#define em emplace
#define eb emplace_back
#define pb push_back
#define all(x) (x).begin(),(x).end()

ll n , m;
ll drink[1002];
vl E[1002];
vl dp[1002];// Gọi dp[i][j] là số dzumbus nhỏ nhất để có chính xác j người uống trong cây con gốc i
vl total_min(vl a,  vl b){
    vl temp(a.size() + b.size() - 1,inf);
    foru(i,0,a.size() - 1){
        foru(j,0,b.size() - 1){
            temp[i + j] = min(temp[i + j],a[i] + b[j]);
        }
    }
    return temp;
}
void process(ll g,ll before){
    dp[g] = {0,drink[g]};
    for(ll c : E[g]){
        if(c == before) continue;
        process(c,g);
        dp[g] = total_min(dp[g],dp[c]);
    }
}


int main(void){
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif //ONLINE_JUDGE
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    foru(i,1,n) cin >> drink[i];
    ll a , b , q;
    foru(i,1,m){
        cin >> a >> b;
        E[a].eb(b);
        E[b].eb(a);
    }
    process(1,-1);
    cin >> q;
    while(q--){
        cin >> a;
        ford(j,n,0){
            if(dp[1][j] <= a){
                cout << j <<'\n';
                break;
            }
        }
    }
}

Compilation message

dzumbus.cpp: In function 'vl total_min(vl, vl)':
dzumbus.cpp:22:38: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define foru(i,a,b) for(ll i = a ; i <= b;i++)
......
   37 |     foru(i,0,a.size() - 1){
      |          ~~~~~~~~~~~~~~~~             
dzumbus.cpp:37:5: note: in expansion of macro 'foru'
   37 |     foru(i,0,a.size() - 1){
      |     ^~~~
dzumbus.cpp:22:38: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define foru(i,a,b) for(ll i = a ; i <= b;i++)
......
   38 |         foru(j,0,b.size() - 1){
      |              ~~~~~~~~~~~~~~~~         
dzumbus.cpp:38:9: note: in expansion of macro 'foru'
   38 |         foru(j,0,b.size() - 1){
      |         ^~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 1516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2892 KB Output isn't correct
2 Halted 0 ms 0 KB -