Submission #792390

#TimeUsernameProblemLanguageResultExecution timeMemory
792390bLICDžumbus (COCI19_dzumbus)C++17
0 / 110
28 ms10580 KiB
/** * Author: Anil Byar **/ #include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; using namespace std; // template<class T> // using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(x) (int)(x).size() #define uniq(v) v.erase(unique(all(v)), v.end()) #define ft first #define sd second #define pb push_back #define eb emplace_back // Source: https://codeforces.com/blog/entry/68809 // { start void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif // } end typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<pii> vii; typedef vector<ll> vl; typedef vector<pll> vll; typedef vector<vi> vvi; typedef vector<vii> vvii; typedef vector<vl> vvl; #define dbg if(0) const ll MOD = 1e9+7; const ll MOD9 = 998244353; const ll INFLL = 1e18+5; const int INF = 1e9; void printbit(int x, int len) {string s="\n";while(len--){s=((x%2)?'1':'0')+s;x/=2;} cout<<s;} ll power(ll x, ll y, ll mod){if (y==0) return 1;ll ret = power(x, y/2, mod);ret *= ret;ret%=mod;if (y&1) ret *= x;return ret%mod;} ll modinv(ll x, ll mod = MOD) {return power(x, mod-2, mod);} template<class T> bool chmin(T& a, T b){return (a>b?a=b,1:0);} template<class T> bool chmax(T& a, T b){return (a<b?a=b,1:0);} template<class T> istream& operator>>(istream&in, vector<T>&v){ for (T& x:v) in>>x; return in; } template<class T> ostream& operator<<(ostream&out, vector<T>&v){ for (T& x:v) out<<x<<' '; cout<<'\n'; return out; } // use ?: with brackets (?:) // check for overflow // think about dp // Read the statement carefully const int N = 1001; vi adj[N]; vvl dp[N]; ll val[N]; bool vis[N]; /* dp[n][0] = node n is neither relaxed nor exchanging. dp[n][1] = node n is relaxed but not exchanging. dp[n][2] = node n is relaxed and exchanging. */ vvl merge(const vvl& a, const vvl& b){ vvl res(4, vl(sz(a[0])+sz(b[0])-1, INFLL)); for (int i = 0;i<sz(a[0]);i++){ for (int j =0;j<sz(b[0]);j++){ chmin(res[0][i+j], a[0][i] + min({b[0][j], b[1][j], b[2][j]})); chmin(res[1][i+j], a[1][i] + b[0][j]); chmin(res[3][i+j], a[3][i] + b[0][j]); if (j) chmin(res[3][i+j], a[3][i] + b[1][j-1]); chmin(res[3][i+j], a[3][i] + b[2][j]); chmin(res[2][i+j], a[2][i] + b[0][j]); if (j) chmin(res[2][i+j], a[3][i] + b[1][j-1]); chmin(res[2][i+j], a[3][i] + b[2][j]); assert(min({res[0][i+j], res[1][i+j], res[2][i+j]})>=0); } } return res; } vl diff_merge(const vl& a, const vl& b){ vl res(sz(a) + sz(b) - 1, INFLL); for (int i = 0;i<sz(a);i++) for (int j = 0;j<sz(b);j++) { chmin(res[i+j], a[i] + b[j]); assert(res[i+j]>=0); } return res; } void dfs(int node, int p){ vis[node] = true; vvl res(4, vl(1)); res[2][0] = INFLL; for (int x:adj[node]) if (x!=p){ dfs(x, node); res = merge(res, dp[x]); // debug(node, x, res); } for (int i = 0;i<sz(res[1]);i++) if (res[1][i]!=INFLL) res[1][i] += val[node]; res[0].push_back(INFLL); res[1].push_back(INFLL); for (ll& x:res[2]) if (x!=INFLL) x += val[node]; res[2].insert(res[2].begin(), 0); // res[2][1] = INFLL; // debug(node, res); dp[node] = res; } void solve(){ int n, m;cin>>n>>m; for (int i = 1;i<=n;i++) cin>>val[i]; for (int i = 0;i<m;i++){ int a, b;cin>>a>>b; adj[a].pb(b); adj[b].pb(a); } vl res(1); for (int j = 1;j<=n;j++){ if (vis[j]) continue; dfs(j, 0); debug(j); for (int i = sz(dp[j][0])-1;i>=0;i--) chmin(dp[j][0][i], min(dp[j][1][i], dp[j][2][i])); for (int i = sz(dp[j][0])-2;i>=0;i--) chmin(dp[j][0][i], dp[j][0][i+1]); res = diff_merge(res, dp[j][0]); } for (int i = sz(res) - 2;i>=0;i--){ chmin(res[i], res[i+1]); } debug(res); int q;cin>>q; while(q--){ ll av;cin>>av; auto ind = upper_bound(all(res), av) - res.begin() - 1; cout<<ind<<'\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define ONLINE_JUDGE #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); freopen("debug.dbg", "w", stderr); int tt = clock(); #endif int t=1, i = 1; // cin>>t; while(t--){ // cout<<"Case #"<<i++<<": "; solve(); cout<<'\n'; } #ifndef ONLINE_JUDGE cerr << "TIME = " << (float)(clock() - tt)/CLOCKS_PER_SEC << endl; tt = clock(); #endif }

Compilation message (stderr)

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:205:14: warning: unused variable 'i' [-Wunused-variable]
  205 |     int t=1, i = 1;
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...