oj.uz

Submission #1097257

# Submission time Handle Problem Language Result Execution time Memory
1097257 2024-10-06T15:23:54 Z hickwhither Džumbus (COCI19_dzumbus) C++17
0 / 110
 1000 ms 10180 KB 
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int INF = 1e9+7;
const int MAXN = 1e3+3;

int n, m, q;
struct Edge
{
    int u, v;
    Edge(){}
    Edge(int _u, int _v): u(_u), v(_v) {}
    int other(const int x){return x^u^v;}
} edge[MAXN] ;

vector<int> e[MAXN];
int s[MAXN];

#define minimize(a,b) a=min(a,b)

int dp[MAXN][MAXN][2];
int lst[MAXN][2];

void dfs(int u=1, int p=0){
    dp[u][0][0] = 0;
    dp[u][0][1] = dp[u][1][1] = s[u];
    
    for(int &z: e[u]){
        int v = edge[z].other(u);
        
        if(v == p) continue;
        dfs(v, u);

        for(int i=0; i<=n; ++i)
            lst[i][0] = dp[u][i][0],
            lst[i][1] = dp[u][i][1];
        
        for(int U=0; U<=n; ++U){
            for(int V=0; V<=n; ++V){
                minimize(dp[u][U+V][0], lst[U][0] + dp[v][V][0]);
                minimize(dp[u][U+V][0], lst[U][0] + dp[v][V][1]);
                
                minimize(dp[u][U+V][1], lst[U][1] + dp[v][V][0]);
                minimize(dp[u][U+V][1], lst[U][1] + dp[v][V][1]);

                minimize(dp[u][U+V+2][1], lst[U][0] + dp[v][V][0] + s[u] + s[v]);
            }
        }
    }
}


signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    if(fopen("*.inp", "r")){
        freopen("*.inp", "r",stdin);
        freopen("*.out", "w",stdout);
    }

    cin >> n >> m;
    for(int i=1; i<=n; ++i) cin >> s[i];
    for(int u, v, i=0; i<m; ++i){
        cin >> edge[i].u >> edge[i].v;
        e[edge[i].u].emplace_back(i);
        e[edge[i].v].emplace_back(i);
    }

    memset(dp, 0x3f, sizeof(dp));
    dfs();
    // cout << "***\n";

    // for(int i=1; i<=n; ++i){
    //     cout << i << "**\n";
    //     for(int j=0; j<=n; ++j) cout << dp[i][j][0] << ' '; cout << '\n';
    //     for(int j=0; j<=n; ++j) cout << dp[i][j][1] << ' '; cout << '\n';
    //     cout << '\n';
    // }
    
    cin >> q;
    while(q--){
        int x;cin >> x;
        bool fl = 1;
        for(int i=n; i>1; --i)
            if(dp[1][i][0]<=x || dp[1][i][1]<=x){
                cout << i << '\n';
                fl = 0;
                break;
            }
        if(fl) cout << "0\n";
    }

    return 0;
}

Compilation message

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:66:13: warning: unused variable 'u' [-Wunused-variable]
   66 |     for(int u, v, i=0; i<m; ++i){
      |             ^
dzumbus.cpp:66:16: warning: unused variable 'v' [-Wunused-variable]
   66 |     for(int u, v, i=0; i<m; ++i){
      |                ^
dzumbus.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen("*.inp", "r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen("*.out", "w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1034 ms 8280 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 1034 ms 8280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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