Submission #677347

#	Time	Username	Problem	Language	Result	Execution time	Memory
677347		nnhzzz	Džumbus (COCI19_dzumbus)	C++14	110 / 110	399 ms	12068 KiB

dzumbus

/*
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) { // v is parent of 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])   // v was not used, enable 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])  // both v and u were not used, enable both
                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])   // v is used but u is not used
                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);
    }

    /// since we need to deal with an edge (a pair of exchange, we work on the parent of the node
    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. This can be optimized to lg(N)
        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;

}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30