Submission #643089

#	Time	Username	Problem	Language	Result	Execution time	Memory
643089		htphong0909	Džumbus (COCI19_dzumbus)	C++17	0 / 110	268 ms	49228 KiB

dzumbus

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define db long double
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define BIT(x, pos) (((x)>>(pos)) & 1LL)
#define _(x) (1LL<<(x))
#define bitCnt(x) __builtin_popcountll(x)
#define turnOn(x, pos) ((x) = (_(pos)))
#define turnOff(x, pos) ((x) &= ~(_(pos)))
#define flipBit(x, pos) ((x) ^= (_(pos)))
#define lowBit(x) ((x) & (-x))
#define turnAll(x) (_(x)-1LL)
#define FOR(i, x, n) for(int i=x; i<n; i++)
#define F0R(i, n) FOR(i,0,n)
#define ROF(i, x, n) for(int i=n-1; i>=x; i--)
#define R0F(i, n) ROF(i,0,n)

const int INF = (int) 1E18;
const db inf = (db) 1E100;
const int MOD = (int) 1E9 + 7;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<pair<int, int>> vpii;

void File() {
#define file "test"
    freopen(file".in", "r", stdin);
    freopen(file".out", "w", stdout);
}

int expo(int a, int b, int mod) {
    int res = 1;
    while (b > 0) {
        if (b & 1)res = (res * a) % mod;
        a = (a * a) % mod;
        b = b >> 1;
    }
    return res;
}

int mminvprime(int a, int b) { return expo(a, b - 2, b); }

int mod_add(int a, int b, int m) {
    a = a % m;
    b = b % m;
    return (((a + b) % m) + m) % m;
}

int mod_mul(int a, int b, int m) {
    a = a % m;
    b = b % m;
    return (((a * b) % m) + m) % m;
}

int mod_sub(int a, int b, int m) {
    a = a % m;
    b = b % m;
    return (((a - b) % m) + m) % m;
}

int mod_div(int a, int b, int m) {
    a = a % m;
    b = b % m;
    return (mod_mul(a, mminvprime(b, m), m) + m) % m;
}

/// ======================================================= - TEMPLATE - ======================================================= ///

int n, m;
vector <int> D;
vector <vector<int>> adj;
int G[1001][1001] = {0};
int F[1001][1001][3] = {0};
int bestG[1001][1001] = {0};
int bestF[1001][1001] = {0};
int Gall[1001] = {0};

void dfs(int u, int par)
{
    //cerr << u << " -------------------" << endl;
    F[u][0][1] = D[u];
    G[u][0] = 0;
    for (int v : adj[u])
    {
        if (v == par) continue;
        dfs(v, u);
        for (int i = 1; i <= n; i++)
        {
            if (F[v][i][0] >= INF) F[v][i][0] -= 1e10;
            if (F[v][i][1] >= INF) F[v][i][1] -= 1e10;
            if (G[v][i] >= INF) G[v][i] -= 1e10;
            if (i >= 2) F[u][i][0] = min(F[u][i][0], min(F[v][i - 2][1] + D[u], F[v][i - 1][0] + D[u]));
            F[u][i][1] = min(F[u][i][1], G[v][i] + D[u]);
            G[u][i] = min(G[u][i], min(F[v][i][0], G[v][i]));
            //cerr << u << " " << i << " " << G[u][i] << " " << F[u][i][0] << endl;
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //File();
    cin >> n >> m;
    D.assign(n + 1, 0);
    adj.assign(n + 1, vector <int>());
    for (int i = 1; i <= n; i++)
    {
        cin >> D[i];
    }
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    memset(F, 0x3f, sizeof(F));
    memset(G, 0x3f, sizeof(G));
    memset(bestG, 0x3f, sizeof(bestG));
    memset(bestF, 0x3f, sizeof(bestF));
    dfs(1, 0);
    vector <pair<int, int>> cur;
    cur.push_back({-INF, 0});
    for (int i = 1; i <= n; i++)
    {
        cur.push_back({min(F[1][i][1], G[1][i]), i});
        //cerr << i << " " << min(F[1][i][0], G[1][i]) << endl;
    }
    sort(all(cur));
    vector <int> temp(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cur[i].second = max(cur[i - 1].second, cur[i].second);
        temp[i] = cur[i].first;
    }
    int q;
    cin >> q;
    while(q--)
    {
        int s;
        cin >> s;
        int pos = upper_bound(all(temp), s) - temp.begin();
        pos--;
        cout << cur[pos].second << endl;
    }
    return 0;
}
/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⢿⣿⣿⠿⠛⠿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠟⠉⠄⣀⡤⢤⣤⣈⠁⣠⡔⠶⣾⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡿⠛⠋⠁⠄⠄⠄⣼⣿⠁⡀⢹⣿⣷⢹⡇⠄⠎⣿⣿⣿
⣿⣿⣿⠿⠛⠉⠁⠄⠄⠄⠄⠄⠄⠄⠹⣇⣀⣡⣾⣿⡿⠉⠛⠒⠒⠋⠉⢸
⡿⠋⠁⠄⠄⢀⣤⣤⡀⠄⠄⠄⠄⠄⠄⠈⠙⠛⠛⠉⠄⠄⠄⠄⠄⠄⠄⠈
⠄⠄⠄⠄⠄⢹⣧⡈⠿⣷⣄⣀⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⣠⢄⣾
⠄⠄⠄⠄⠄⠈⠻⢿⣶⣌⣙⡛⠛⠿⠶⠶⠶⠶⠶⠖⣒⣒⣚⣋⡩⢱⣾⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠈⠉⠛⠛⠛⠻⠿⠿⠟⠛⠛⠛⠉⢉⣥⣶⣾⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠒⠶⣿⣿⣿⣿⣿⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿
⣿⡿⠛⠛⠛⢻⣿⠿⠛⠛⠛⢿⣿⣿⡿⠛⠛⠛⢻⡟⠛⣿⡿⠛⣻⣿⣿⣿
⡟⠄⣼⣿⣿⣿⡇⠄⣾⣿⣧⠄⢻⡏⠄⣼⣿⣿⣿⡇⠄⡟⢀⣴⣿⣿⣿⣿
⡇⠄⣿⣿⣿⣿⡄⠄⣿⣿⣿⠄⢸⡇⠄⣿⣿⣿⣿⡇⠄⣀⠈⢻⣿⣿⣿⣿
⣿⣄⠈⠙⠛⢻⣧⡄⠙⠛⠉⣠⣿⣷⣄⠈⠙⠛⢹⡇⠄⣿⣧⠄⠻⣿⣿⣿

 ___  ___  _________        ________  ___  ___  ________  ________   ________          ________  ________  ________  ________
|\  \|\  \|\___   ___\     |\   __  \|\  \|\  \|\   __  \|\   ___  \|\   ____\        |\   __  \|\   ____\|\   __  \|\   __  \
\ \  \\\  \|___ \  \_|     \ \  \|\  \ \  \\\  \ \  \|\  \ \  \\ \  \ \  \___|        \ \  \|\  \ \  \___|\ \  \|\ /\ \  \|\  \
 \ \   __  \   \ \  \       \ \   ____\ \   __  \ \  \\\  \ \  \\ \  \ \  \  ___       \ \  \\\  \ \  \    \ \   __  \ \  \\\  \
  \ \  \ \  \   \ \  \       \ \  \___|\ \  \ \  \ \  \\\  \ \  \\ \  \ \  \|\  \       \ \  \\\  \ \  \____\ \  \|\  \ \  \\\  \
   \ \__\ \__\   \ \__\       \ \__\    \ \__\ \__\ \_______\ \__\\ \__\ \_______\       \ \_______\ \_______\ \_______\ \_______\
    \|__|\|__|    \|__|        \|__|     \|__|\|__|\|_______|\|__| \|__|\|_______|        \|_______|\|_______|\|_______|\|_______|
*/		

Compilation message (stderr)

dzumbus.cpp: In function 'void File()':
dzumbus.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen(file".in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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