oj.uz

Submission #704798

# Submission time Handle Problem Language Result Execution time Memory
704798 2023-03-03T03:43:39 Z becaido Džumbus (COCI19_dzumbus) C++17
110 / 110
 487 ms 10844 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1005;
const ll INF = 1e18;

int n, m, q;
int a[SIZE];
bool vs[SIZE];
vector<ll> dp[SIZE][2], ans;
vector<int> adj[SIZE];

void Merge(vector<ll> &A, vector<ll> &B, vector<ll> &C, vector<ll> &D, int wv, int wson) {
    int sA = A.size() - 1, sB = B.size() - 1, sC = C.size() - 1, sD = D.size() - 1;
    auto updA = [&](int i, ll x) {
        while (A.size() <= i) A.pb(INF);
        A[i] = min(A[i], x);
    };
    auto updB = [&](int i, ll x) {
        while (B.size() <= i) B.pb(INF);
        B[i] = min(B[i], x);
    };
    for (int i = sB + max(sC, sD) + 1; i >= 0; i--) {
        for (int j = 0; j <= sC; j++) {
            if (i - j <= sB && i - j >= 0) updB(i, B[i - j] + C[j]);
            if (i - j - 1 >= 0 && i - j - 1 <= sB) updB(i, B[i - j - 1] + C[j] + wson);
        }
        for (int j = 0; j <= sD && i - j >= 0; j++) if (i - j <= sB) updB(i, B[i - j] + D[j]);
    }
    FOR (i, 0, sA) FOR (j, 0, sC) updB(i + j + 2, A[i] + C[j] + wv + wson);
    FOR (i, 0, sA) FOR (j, 0, sD) updB(i + j + 1, A[i] + D[j] + wv);
    for (int i = sA + max(sC, sD); i >= 0; i--) {
        for (int j = 0; j <= sC && i - j >= 0; j++) if (i - j <= sA) updA(i, A[i - j] + C[j]);
        for (int j = 0; j <= sD && i - j >= 0; j++) if (i - j <= sA) updA(i, A[i - j] + D[j]);
    }
}

void Merge(vector<ll> &A, vector<ll> &C, vector<ll> &D) {
    int sA = A.size() - 1, sC = C.size() - 1, sD = D.size() - 1;
    auto updA = [&](int i, ll x) {
        while (A.size() <= i) A.pb(INF);
        A[i] = min(A[i], x);
    };
    for (int i = sA + max(sC, sD); i >= 0; i--) {
        for (int j = 0; j <= sC && i - j >= 0; j++) if (i - j <= sA) updA(i, A[i - j] + C[j]);
        for (int j = 0; j <= sD && i - j >= 0; j++) if (i - j <= sA) updA(i, A[i - j] + D[j]);
    }
}

void dfs(int pos) {
    vs[pos] = 1;
    dp[pos][0].resize(1, 0);
    dp[pos][1].resize(1, INF);
    for (int np : adj[pos]) if (!vs[np]) {
        dfs(np);
        Merge(dp[pos][0], dp[pos][1], dp[np][0], dp[np][1], a[pos], a[np]);
    }
}

void solve() {
    cin >> n >> m;
    FOR (i, 1, n) cin >> a[i];
    while (m--) {
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    ans.resize(1, 0);
    FOR (i, 1, n) if (!vs[i]) {
        dfs(i);
        Merge(ans, dp[i][0], dp[i][1]);
    }
    ans.resize(n + 1, INF);
    for (int i = n - 1; i >= 0; i--) ans[i] = min(ans[i], ans[i + 1]);
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << upper_bound(ans.begin(), ans.end(), x) - ans.begin() - 1 << '\n';
    }
}

int main() {
    Waimai;
    solve();
}

Compilation message

dzumbus.cpp: In lambda function:
dzumbus.cpp:34:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |         while (A.size() <= i) A.pb(INF);
      |                ~~~~~~~~~^~~~
dzumbus.cpp: In lambda function:
dzumbus.cpp:38:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |         while (B.size() <= i) B.pb(INF);
      |                ~~~~~~~~~^~~~
dzumbus.cpp: In lambda function:
dzumbus.cpp:59:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |         while (A.size() <= i) A.pb(INF);
      |                ~~~~~~~~~^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 6948 KB Output is correct
2 Correct 375 ms 7976 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 6948 KB Output is correct
2 Correct 375 ms 7976 KB Output is correct
3 Correct 487 ms 10844 KB Output is correct
4 Correct 287 ms 9508 KB Output is correct
5 Correct 255 ms 8312 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2488 KB Output is correct
2 Correct 33 ms 2268 KB Output is correct
3 Correct 35 ms 2636 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 6948 KB Output is correct
2 Correct 375 ms 7976 KB Output is correct
3 Correct 487 ms 10844 KB Output is correct
4 Correct 287 ms 9508 KB Output is correct
5 Correct 255 ms 8312 KB Output is correct
6 Correct 35 ms 2488 KB Output is correct
7 Correct 33 ms 2268 KB Output is correct
8 Correct 35 ms 2636 KB Output is correct
9 Correct 41 ms 2892 KB Output is correct
10 Correct 46 ms 3432 KB Output is correct
11 Correct 39 ms 2888 KB Output is correct