oj.uz

Submission #447173

# Submission time Handle Problem Language Result Execution time Memory
447173 2021-07-24T23:28:34 Z gmyu Džumbus (COCI19_dzumbus) C++14
110 / 110
 570 ms 12116 KB 
/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/COCI19_dzumbus
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <string.h>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define ff  first
#define ss  second
#define pb  push_back
#define sz(x)   (int)(x).size()

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 1007
#define MAXE 100007

bool debug;

int N, M;
ll dp[MAXV][MAXV][2];   /// dp[i,j,0/1] at node i total j people exchanged solutuion, whether note i is/is not used, what's the min cost
ll dp2[MAXV][2];
ll subsz[MAXV];         /// subtree size
vi adj[MAXV];
ll d[MAXV];
int visited[MAXV];

int ans = 0;

void update(int v, int u) {
    for(int i=0; i<=subsz[v]+subsz[u]; i++) { dp2[i][0]=INF; dp2[i][1]= INF;}

    for(int i=0; i<=subsz[v]; i++) {
        for(int j=0; j<=subsz[u]; j++) {
            dp2[i+j][0] = min(dp2[i+j][0], dp[v][i][0] + min(dp[u][j][0], dp[u][j][1]));
            dp2[i+j][1] = min(dp2[i+j][1], dp[v][i][1] + min(dp[u][j][0], dp[u][j][1]));
            if(i+1<=subsz[v])
                dp2[i+j+1][1] = min(dp2[i+j+1][1], dp[v][i][0] + d[v] + dp[u][j][1]);
            if(i+1<=subsz[v] && j+1<=subsz[u])
                dp2[i+j+2][1] = min(dp2[i+j+2][1], dp[v][i][0] + d[v] + d[u]+ dp[u][j][0]);
            if(j+1<=subsz[u])
                dp2[i+j+1][1] = min(dp2[i+j+1][1], dp[v][i][1] + d[u] + dp[u][j][0]);
        }
    }

    for(int i=0; i<=subsz[v]+subsz[u]; i++) {
        dp[v][i][0] = dp2[i][0]; dp[v][i][1] = dp2[i][1];
        if(debug) cout << u << " : " << dp[v][i][0] << " , " << dp[v][i][1] << endl;
     }

}

void dfs(int v, int p) {
    visited[v] = 1;
    dp[v][0][0] = 0; dp[v][1][0] = INF;
    dp[v][0][1] = INF; dp[v][1][1] = INF;
    subsz[v] = 1;

    for(auto x : adj[v]) {
        if(x == p || visited[x]) continue;
        dfs(x, v);
    }

    update(p, v);
    subsz[p] += subsz[v];

}

int main() {
    debug = false;
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> M;
    d[0] = INF;
    for(int i=1; i<=N; i++) cin >> d[i];

    for(int i=1; i <= M; i++){
        int a, b; cin >> a >> b;
        adj[a].pb(b); adj[b].pb(a);
    }

    dp[0][0][0] = 0; dp[0][1][0] = INF;
    dp[0][0][1] = INF; dp[0][1][1] = INF;
    for(int i=1; i<=N; i++) {
        if(visited[i]) continue;
        dfs(i, 0);
    }

    if(debug) {
        cout << "ans" << endl;
        for(int k=0; k<=N; k++) cout << dp[0][k][0] << " " << dp[0][k][1] << endl;
        cout << "---" << endl;
    }

    int Q; cin >> Q;
    for(int i=1; i<= Q; i++) {
        int S; cin >> S;
        int k;
        // too lazy, so I'm doing a for-loop here
        for(k=N; k>=0; k--) {
            if(dp[0][k][0]>S && dp[0][k][0]>S) continue;
            break;
        }
        cout << k << endl;
    }

    if(debug) cout << endl << "EOL" << endl;

}

/*

3 2
1 2 3
1 2
1 3
3
2
3
5

14 13
2 3 4 19 20 21 5 22 6 7 23 8 10 14
1 2
1 3
1 4
2 5
2 6
3 7
3 8
3 9
4 10
8 11
10 13
10 12
12 14
3
45
44
23


*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8780 KB Output is correct
2 Correct 13 ms 9444 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8780 KB Output is correct
2 Correct 13 ms 9444 KB Output is correct
3 Correct 391 ms 12116 KB Output is correct
4 Correct 394 ms 11392 KB Output is correct
5 Correct 570 ms 10744 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 2780 KB Output is correct
2 Correct 340 ms 2616 KB Output is correct
3 Correct 359 ms 2984 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8780 KB Output is correct
2 Correct 13 ms 9444 KB Output is correct
3 Correct 391 ms 12116 KB Output is correct
4 Correct 394 ms 11392 KB Output is correct
5 Correct 570 ms 10744 KB Output is correct
6 Correct 340 ms 2780 KB Output is correct
7 Correct 340 ms 2616 KB Output is correct
8 Correct 359 ms 2984 KB Output is correct
9 Correct 384 ms 6760 KB Output is correct
10 Correct 400 ms 7316 KB Output is correct
11 Correct 557 ms 6972 KB Output is correct