oj.uz

Submission #589808

# Submission time Handle Problem Language Result Execution time Memory
589808 2022-07-05T09:48:24 Z Huy Džumbus (COCI19_dzumbus) C++17
110 / 110
 45 ms 11252 KB 
/// no sound please
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define pic pair<int,char>
#define fi first
#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const ll N = (int)1e9 + 1;
const int maxN = (int)2e5 + 2;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infty = 1e18 + 7;
const int base = (int)4e5;

void InputFile()
{
    //freopen("IELTS.inp","r",stdin);
    //freopen("IELTS.out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int n,m;
int d[2000];
vector<int> adj[2000];
vector<ll> dp[2000][3];
/// 0 : ko chon i
/// 1 : chon i va i ke dinh khac
/// 2 : chon i nhung i dell ke dinh khac
int grp = 0;
int subsz[2000];

vector<ll> f;

void Read()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> d[i];
    }
    for(int i = 1; i <= m; i++)
    {
        int x,y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
}


void PreDFS(int u,int p)
{
    subsz[u] = 1;
    for(int v : adj[u])
    {
        if(v == p) continue;
        PreDFS(v,u);
        subsz[u] += subsz[v];
    }
}

void DFS(int u,int p)
{
    dp[u][0] = {0,infty};
    dp[u][1] = {infty,infty};
    dp[u][2] = {infty,d[u]};
    int ss = 1;
    for(int v : adj[u])
    {
        if(v == p) continue;
        DFS(v,u);
        vector<ll> vc[3];
        vc[0].resize(ss + subsz[v] + 1,infty);
        vc[1].resize(ss + subsz[v] + 1,infty);
        vc[2].resize(ss + subsz[v] + 1,infty);
        for(int i = 0;i <= ss;i++)
        {
            for(int j = 0;j <= subsz[v];j++)
            {
                vc[0][i+j] = min(vc[0][i+j],dp[u][0][i] + dp[v][0][j]);
                vc[0][i+j] = min(vc[0][i+j],dp[u][0][i] + dp[v][1][j]);

                vc[1][i+j] = min(vc[1][i+j],dp[u][1][i] + dp[v][0][j]);
                vc[1][i+j] = min(vc[1][i+j],dp[u][1][i] + dp[v][1][j]);
                vc[1][i+j] = min(vc[1][i+j],dp[u][1][i] + dp[v][2][j]);
                vc[1][i+j] = min(vc[1][i+j],dp[u][2][i] + dp[v][2][j]);
                vc[1][i+j] = min(vc[1][i+j],dp[u][2][i] + dp[v][1][j]);

                vc[2][i+j] = min(vc[2][i+j],dp[u][2][i] + dp[v][0][j]);
            }
        }
        swap(vc[0],dp[u][0]);
        swap(vc[1],dp[u][1]);
        swap(vc[2],dp[u][2]);
        ss += subsz[v];
    }
}

void Solve()
{
    for(int i = 1;i <= n;i++)
    {
        if(subsz[i] == 0) PreDFS(i,i);
    }

    int su = 0;
    f = {0};
    vector<ll> sf;
    for(int u = 1;u <= n;u++)
    {
        if(dp[u][0].empty())
        {
            DFS(u,u);
            sf.resize(su + subsz[u] + 1,infty);
            for(int i = 0;i <= su;i++)
            {
                for(int j = 0;j <= subsz[u];j++)
                {
                    sf[i+j] = min(sf[i+j],f[i] + dp[u][0][j]);
                    sf[i+j] = min(sf[i+j],f[i] + dp[u][1][j]);
                }
            }
            swap(sf,f);
            sf.clear();
            su += subsz[u];
        }
    }

    for(int i = f.size() - 2;i >= 0;i--)
    {
        f[i] = min(f[i],f[i+1]);
    }

    int q;
    cin >> q;
    while(q--)
    {
        int val;
        cin >> val;
        cout << upper_bound(f.begin(),f.end(),val) - f.begin() - 1 <<'\n';
    }
}

void Debug()
{

}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    //Prepare();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Correct 10 ms 8400 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Correct 10 ms 8400 KB Output is correct
3 Correct 41 ms 11252 KB Output is correct
4 Correct 44 ms 9824 KB Output is correct
5 Correct 45 ms 9032 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1344 KB Output is correct
2 Correct 30 ms 2376 KB Output is correct
3 Correct 33 ms 2764 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7252 KB Output is correct
2 Correct 10 ms 8400 KB Output is correct
3 Correct 41 ms 11252 KB Output is correct
4 Correct 44 ms 9824 KB Output is correct
5 Correct 45 ms 9032 KB Output is correct
6 Correct 30 ms 1344 KB Output is correct
7 Correct 30 ms 2376 KB Output is correct
8 Correct 33 ms 2764 KB Output is correct
9 Correct 36 ms 3204 KB Output is correct
10 Correct 37 ms 3488 KB Output is correct
11 Correct 39 ms 3196 KB Output is correct