oj.uz

Submission #491555

# Submission time Handle Problem Language Result Execution time Memory
491555 2021-12-03T05:29:38 Z Croco Džumbus (COCI19_dzumbus) C++17
110 / 110
 53 ms 26820 KB 
#include <bits/stdc++.h>
#define int long long int
#define ll long long int

using namespace std;

const int N = 1e3 + 5;

int n,m;
vector<int> g[N];
int dp[N][N][3];
bool vis[N];
int cost[N];
int sz[N];
int inf = 1e9 + 5;

void dfs(int v)
{
    vis[v] = 1;
    dp[v][0][0] = 0;
    dp[v][1][1] = cost[v];
    sz[v] = 1;
    for(auto x : g[v])
    {
        if(vis[x])
            continue;
        dfs(x);
        for(int i=sz[v];i>=0;i--)
        {
            for(int j=0;j<=sz[x];j++)
            {
                dp[v][i+j][0] = min(dp[v][i+j][0] , dp[v][i][0] + min(dp[x][j][0] , dp[x][j][2]));
                dp[v][i+j][1] = min(dp[v][i+j][1] , dp[v][i][1] + min(dp[x][j][0] , dp[x][j][2]));
                dp[v][i+j][2] = min(dp[v][i+j][2] , dp[v][i][1] + min(dp[x][j][1] , dp[x][j][2]));
                dp[v][i+j][2] = min(dp[v][i+j][2] , dp[v][i][2] + min({dp[x][j][1],dp[x][j][0],dp[x][j][2]}));
            }
        }
        sz[v] += sz[x];
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>cost[i];
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int tot = 0;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = inf;
    dp[0][0][0] = 0;
    for(int x=1;x<=n;x++)
    {
        if(vis[x])
            continue;
        dfs(x);
        int v = 0;
        for(int i=tot;i>=0;i--)
        {
            for(int j=0;j<=sz[x];j++)
            {
                dp[v][i+j][0] = min(dp[v][i+j][0] , dp[v][i][0] + min(dp[x][j][0] , dp[x][j][2]));
            }
        }
        tot += sz[x];
    }
    for(int i=n-1;i>=0;i--)
        dp[0][i][0] = min(dp[0][i][0] , dp[0][i+1][0]);
    int q;
    cin>>q;
    while(q--)
    {
        int val;
        cin>>val;
        int best = 0,low = 0;
        int high = n;
        while(low <= high)
        {
            int mid = (low + high)/2;
            if(dp[0][mid][0] <= val)
            {
                best = mid;
                low = mid+1;
            }
            else
                high = mid-1;
        }
        cout << best << "\n";
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24028 KB Output is correct
2 Correct 15 ms 24100 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24028 KB Output is correct
2 Correct 15 ms 24100 KB Output is correct
3 Correct 47 ms 26056 KB Output is correct
4 Correct 53 ms 26820 KB Output is correct
5 Correct 53 ms 26444 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1784 KB Output is correct
2 Correct 35 ms 2892 KB Output is correct
3 Correct 36 ms 3268 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24028 KB Output is correct
2 Correct 15 ms 24100 KB Output is correct
3 Correct 47 ms 26056 KB Output is correct
4 Correct 53 ms 26820 KB Output is correct
5 Correct 53 ms 26444 KB Output is correct
6 Correct 36 ms 1784 KB Output is correct
7 Correct 35 ms 2892 KB Output is correct
8 Correct 36 ms 3268 KB Output is correct
9 Correct 44 ms 26048 KB Output is correct
10 Correct 53 ms 26640 KB Output is correct
11 Correct 49 ms 26468 KB Output is correct