Submission #413870

#	Time	Username	Problem	Language	Result	Execution time	Memory
413870		arman_ferdous	Džumbus (COCI19_dzumbus)	C++17	0 / 110	65 ms	9548 KiB

dzumbus

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

// #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define fi first
#define se second
#define pb push_back
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()

using ll = long long;
using ii = pair<ll,ll>;

const int N = 1010;
const ll oo = 1e16;

int n, m; ll d[N];
vector<int> g[N];

int vis[N];
void dfs(int u, int f) {
  vis[u] = 1;
  for(int v : g[u]) if(v != f)
    dfs(v, u);
}

vector<ll> dp[2][N], ondp[2][N];

void combine(vector<ll> &x, vector<ll> &y) {
  int szx = sz(x), szy = sz(y);
  vector<ll> ret(szx + szy - 1, oo);
  for(int i = 0; i < szx; i++)
    for(int j = 0; j < szy; j++)
      ret[i + j] = min(ret[i + j], x[i] + y[j]);
  x = ret;
}

void solve(int u, int f) {
  for(int v : g[u]) if(v != f)
    solve(v, u);

  dp[0][u] = {0, oo};
  dp[1][u] = {0, oo};

  for(int v : g[u]) if(v != f) {
    combine(dp[0][u], dp[0][v]);
    combine(dp[1][u], dp[0][v]);
  }

  ondp[0][u] = {0, d[u]};
  ondp[1][u] = {0, d[u]};

  for(int v : g[u]) if(v != f) {
    combine(ondp[0][u], dp[1][v]);
    combine(ondp[1][u], dp[1][v]);
  }
  int sz = sz(dp[0][u]);
  for(int i = 2; i < sz; i++) dp[0][u][i] = min(dp[0][u][i], ondp[0][u][i]);
  int sz1 = sz(dp[1][u]);
  for(int i = 0; i < sz1; i++) dp[1][u][i] = min(dp[1][u][i], ondp[1][u][i]);
}

int main() {
  scanf("%d %d", &n, &m);
  for(int i = 1; i <= n; i++) scanf("%lld", &d[i]);
  for(int i = 0; i < m; i++) {
    int u, v; scanf("%d %d", &u, &v);
    g[u].pb(v); g[v].pb(u);
  }
  vector<int> roots;
  for(int i = 1; i <= n; i++) if(!vis[i]) {
    roots.pb(i); dfs(i, 0);
  }
  for(int u : roots) {
    g[0].pb(u); g[u].pb(0);
  }

  solve(0, -1);
  // for(int i = 0; i <= n + 1; i++)
  //   printf("%d: %lld\n", i, dp[0][0][i]);

  int q; scanf("%d", &q);
  while(q--) {
    ll x; scanf("%lld", &x);
    int lo = 3, hi = sz(dp[0][0]) - 1, idx = 1;
    while(lo <= hi) {
      int mid = lo + hi >> 1;
      if(dp[0][0][mid] <= x) idx = mid, lo = mid + 1;
      else hi = mid - 1;
    }
    printf("%d\n", idx - 1);
  }
  return 0;
}

Compilation message (stderr)

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:89:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |       int mid = lo + hi >> 1;
      |                 ~~~^~~~
dzumbus.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%d %d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:67:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   for(int i = 1; i <= n; i++) scanf("%lld", &d[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~
dzumbus.cpp:69:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     int u, v; scanf("%d %d", &u, &v);
      |               ~~~~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:84:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   int q; scanf("%d", &q);
      |          ~~~~~^~~~~~~~~~
dzumbus.cpp:86:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     ll x; scanf("%lld", &x);
      |           ~~~~~^~~~~~~~~~~~

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