Submission #1120019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120019		smokieboi	Džumbus (COCI19_dzumbus)	C++17	110 / 110	50 ms	26992 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define nl '\n'
#define fu(i,a,b) for(int i=a; i<=b; i++)
#define fd(i,a,b) for(int i=a; i>=b; i--)
#define BIT(i, n) (((n)>>(i))&(1))
#define pii pair<int, int>
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define SZ(V) (int)(V.size())
#define pb push_back
#define eb emplace_back
#define NAME "quan"

int t,n,m,k,q;

const int N = 1e3 + 5;
const int MOD = 1e9 + 7;
const int inf = 1e9 + 7;

void add(int &a, int b) {a+=b; if(a>=MOD) a-=MOD;}
void sub(int &a, int b) {a-=b; if(a<0) a+=MOD;}

int a[N], sz[N], Max[N];
bool vis[N];
vector<int> adj[N];
vector<pair<ll, int>> V;
ll dp[N][N][3];

void dfs(int u){
    vis[u] = true;
    dp[u][0][0] = 0;
    dp[u][1][1] = a[u];
    sz[u] = 1;
    for(int v: adj[u]){
        if(vis[v]) continue;
        dfs(v);
        fd(i, sz[u], 0)
            fd(j, sz[v], 0){
                if(i + j > 1) dp[u][i + j][2] = min(dp[u][i + j][2], dp[u][i][1] + min(dp[v][j][1], dp[v][j][2]));
                if(i + j > 1) dp[u][i + j][2] = min(dp[u][i + j][2], dp[u][i][2] + min({dp[v][j][0], dp[v][j][1], dp[v][j][2]}));
                dp[u][i + j][1] = min(dp[u][i + j][1], dp[u][i][1] + dp[v][j][0]);
                if(j > 1) dp[u][i + j][0] = min(dp[u][i + j][0], dp[u][i][0] + min(dp[v][j][0], dp[v][j][2]));
            }
        sz[u] += sz[v];
    }
}

void nhap(){
    cin >> n >> m;
    fu(i,1,n) cin >> a[i];
    fu(i,1,m){
        int u,v;
        cin >> u >> v;
        adj[u].eb(v);
        adj[v].eb(u);
    }
    memset(dp, 0x3f, sizeof dp);
    dp[0][0][0] = 0;
    fu(u, 1, n)
        if(!vis[u]){
            dfs(u);
            fd(i, sz[0], 0)
                fd(j, sz[u], 2)
                    dp[0][i + j][0] = min(dp[0][i + j][0], dp[0][i][0] + min(dp[u][j][0], dp[u][j][2]));
            sz[0] += sz[u];
        }
    fu(i,2,n) V.eb(dp[0][i][0], i);
    sort(all(V));
    for(int i=0; i<SZ(V); i++)
        Max[i+1] = max(Max[i], V[i].ss);
    cin >> q;
    while(q--){
        ll x;
        cin >> x;
        int p = upper_bound(all(V), make_pair(x, inf)) - V.begin();
        cout << Max[p] << nl;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(NAME".inp", "r")){
       freopen(NAME".inp", "r", stdin);
       freopen(NAME".out", "w", stdout);
    }
    nhap();
}

Compilation message (stderr)

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:88:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |        freopen(NAME".inp", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:89:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |        freopen(NAME".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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