제출 #588277

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
588277		Do_you_copy	Džumbus (COCI19_dzumbus)	C++14	0 / 110	34 ms	9940 KiB

dzumbus

#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

using ll = long long;
using pii = pair <int, int>;

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

const ll Mod = 1000000007;
const int maxN = 5e3 + 1;
const ll inf = 1e18;
int n, m;
bool visited[maxN];
vector <ll> dp[maxN][3];
int a[maxN];

vector <int> adj[maxN];

void predfs(int u){
    visited[u] = 1;
    for (const int &v: adj[u]){
        if (!visited[v]){
            predfs(v);
        }
    }
}

void dfs(int u, int p){
    dp[u][0] = {0, inf};
    dp[u][1] = {a[u], inf};
    dp[u][2] = {inf, inf};
    for (const int &t: adj[u]){
        if (t != p){
            dfs(t, u);
            int s = dp[u][0].size() + dp[t][0].size() - 1;
            vector <ll> tem0(s, inf);
            vector <ll> tem1(s, inf);
            vector <ll> tem2(s, inf);
            for (int i = 0; i < dp[u][0].size(); ++i){
                for (int j = 0; j < dp[t][0].size(); ++j){
                    tem0[i + j] = min(tem0[i + j], dp[u][0][i] + min(dp[t][0][j], min(dp[t][1][j], dp[t][2][j])));
                    tem1[i + j] = min(tem1[i + j], dp[u][1][i] + dp[t][0][j]);
                    tem2[i + j] = min(tem2[i + j], dp[u][2][i] + min(dp[t][2][j], dp[t][0][j]));
                    if (i + j + 1 < tem2.size())
                    tem2[i + j + 1] = min(tem2[i + j + 1], min(dp[u][2][i] + dp[t][1][j], dp[u][1][i] + dp[t][2][j]));
                    if (i + j + 2 < tem2.size())
                    tem2[i + j + 2] = min(tem2[i + j + 2], dp[u][1][i] + dp[t][1][j]);
                }
            }
            dp[u][0] = tem0;
            dp[u][1] = tem1;
            dp[u][2] = tem2;
        }
    }
}

void Init(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    a[0] = INT_MAX;
    for (int i = 1; i <= n; ++i){
        if (!visited[i]){
            predfs(i);
            adj[0].pb(i);
        }
    }
    dfs(0, -1);
    int q; cin >> q; while (q--){
        int s; cin >> s;
        int t = upper_bound(dp[0][0].begin() + 2, dp[0][0].end(), s) - dp[0][0].begin() - 1;
        if (t == 1) --t;
        cout << t << "\n";
    }
}

int main(){
    if (fopen(taskname".txt", "r")){
        freopen(taskname".txt", "r", stdin);
    }
    faster
    //freopen(taskname.inp, "r", stdin)
    //freopen(taskname.out, "w", stdout)
    Init();
}

컴파일 시 표준 에러 (stderr) 메시지

dzumbus.cpp: In function 'void dfs(int, int)':
dzumbus.cpp:50:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for (int i = 0; i < dp[u][0].size(); ++i){
      |                             ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:51:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                 for (int j = 0; j < dp[t][0].size(); ++j){
      |                                 ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:55:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |                     if (i + j + 1 < tem2.size())
      |                         ~~~~~~~~~~^~~~~~~~~~~~~
dzumbus.cpp:57:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                     if (i + j + 2 < tem2.size())
      |                         ~~~~~~~~~~^~~~~~~~~~~~~
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(taskname".txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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