oj.uz

Submission #1120019

# Submission time Handle Problem Language Result Execution time Memory
1120019 2024-11-27T17:31:55 Z smokieboi Džumbus (COCI19_dzumbus) C++17
110 / 110
 50 ms 26992 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24320 KB Output is correct
2 Correct 19 ms 24324 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24320 KB Output is correct
2 Correct 19 ms 24324 KB Output is correct
3 Correct 43 ms 26440 KB Output is correct
4 Correct 45 ms 26960 KB Output is correct
5 Correct 45 ms 26704 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 26152 KB Output is correct
2 Correct 40 ms 26068 KB Output is correct
3 Correct 49 ms 26448 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24320 KB Output is correct
2 Correct 19 ms 24324 KB Output is correct
3 Correct 43 ms 26440 KB Output is correct
4 Correct 45 ms 26960 KB Output is correct
5 Correct 45 ms 26704 KB Output is correct
6 Correct 50 ms 26152 KB Output is correct
7 Correct 40 ms 26068 KB Output is correct
8 Correct 49 ms 26448 KB Output is correct
9 Correct 46 ms 26216 KB Output is correct
10 Correct 47 ms 26992 KB Output is correct
11 Correct 44 ms 26716 KB Output is correct