Submission #469263

#TimeUsernameProblemLanguageResultExecution timeMemory
469263cpp219Džumbus (COCI19_dzumbus)C++14
0 / 110
28 ms8524 KiB
#include<bits/stdc++.h> #define ll long long #define ld long double #define fs first #define sc second #define debug(y) cout<<y,exit(0) using namespace std; typedef pair<ll,ll> LL; const ll N = 1e3 + 9; const ll inf = 1e9 + 7; vector<ll> g[N],dp[2][N],mix[N]; ll n,m,Q,a[N],total,was[N],ans[N]; LL q[200002]; void out(vector<ll> v){ for (ll i = 0;i < v.size();i++) cout<<v[i]<<" "<<i<<"\n"; exit(0); } vector<ll> combine(vector<ll> a,vector<ll> b,ll cond,ll id){ vector<ll> res(a.size() + b.size() - 1,inf); for (ll i = 0;i < a.size();i++){ res[i] = min(res[i],a[i]); for (ll j = 0;j < b.size();j++){ if (i + j == 1) continue; if (cond && (j == 1 || i == 1)) continue; if (!cond && i == 1){ res[i + j] = min(res[i + j],a[i] + dp[0][id][j]); continue; } res[i + j] = min(res[i + j],a[i] + b[j]); } } return res; } void DFS(ll u,ll p){ for (auto i : g[u]) if (i != p) DFS(i,u); dp[0][u] = {inf,a[u]}; dp[1][u] = {0,inf}; //if (u == 1) out(dp[0][1]); for (auto i : g[u]) if (i != p){ dp[0][u] = combine(dp[0][u],mix[i],0,i); dp[1][u] = combine(dp[1][u],mix[i],1,i); } for (ll i = 0;i < dp[0][u].size();i++) mix[u].push_back(min(dp[0][u][i],dp[1][u][i])); } vector<LL> v; void preDFS(ll u,ll p){ was[u] = 1; for (auto i : g[u]) if (i != p) preDFS(i,u); } int main(){ ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0); #define task "test" if (fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } cin>>n>>m; for (ll i = 1;i <= n;i++) cin>>a[i]; while(m--){ ll x,y; cin>>x>>y; g[x].push_back(y); g[y].push_back(x); } for (ll i = 1;i <= n;i++){ if (!was[i]) preDFS(i,-1),g[0].push_back(i); } DFS(0,-1); //out(dp[0][1]); cin>>Q; for (ll i = 1;i <= Q;i++) cin>>q[i].fs,q[i].sc = i; sort(q + 1,q + Q + 1); for (ll i = 0;i < dp[1][0].size();i++){ ll cur = dp[1][0][i]; if (cur != inf) v.push_back({cur,i}); } ll now = 0,sz = v.size(); for (ll i = 1;i <= Q;i++){ while(now < sz && v[now].fs <= q[i].fs) now++; ans[q[i].sc] = max(0ll,v[now - 1].sc); } for (ll i = 1;i <= Q;i++) cout<<ans[i]<<"\n"; } /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */

Compilation message (stderr)

dzumbus.cpp: In function 'void out(std::vector<long long int>)':
dzumbus.cpp:17:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (ll i = 0;i < v.size();i++) cout<<v[i]<<" "<<i<<"\n";
      |                   ~~^~~~~~~~~~
dzumbus.cpp: In function 'std::vector<long long int> combine(std::vector<long long int>, std::vector<long long int>, long long int, long long int)':
dzumbus.cpp:23:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (ll i = 0;i < a.size();i++){
      |                   ~~^~~~~~~~~~
dzumbus.cpp:25:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (ll j = 0;j < b.size();j++){
      |                       ~~^~~~~~~~~~
dzumbus.cpp: In function 'void DFS(long long int, long long int)':
dzumbus.cpp:46:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (ll i = 0;i < dp[0][u].size();i++)
      |                   ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:77:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (ll i = 0;i < dp[1][0].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...