oj.uz

Submission #502748

# Submission time Handle Problem Language Result Execution time Memory
502748 2022-01-06T14:27:35 Z ctd6969 Džumbus (COCI19_dzumbus) C++17
0 / 110
 1000 ms 3404 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(int i = a ; i <= b;i++)
#define ford(i,a,b) for(int 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);
    }
    cin >> q;
    while(q--){
        foru(i,0,n) dp[i].clear();
        cin >> a;
        process(1,-1);
        ford(i,n,0){
            if(dp[1][i] <= a) {
                if(i == 1) cout << 0 <<'\n';
                else cout << i <<'\n';
                break;}
            
        }
    }
}

Compilation message

dzumbus.cpp: In function 'vl total_min(vl, vl)':
dzumbus.cpp:22:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define foru(i,a,b) for(int 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:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define foru(i,a,b) for(int 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 Execution timed out 1066 ms 3404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 3404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 1096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 3404 KB Time limit exceeded
2 Halted 0 ms 0 KB -