Submission #469294

#TimeUsernameProblemLanguageResultExecution timeMemory
469294cpp219Džumbus (COCI19_dzumbus)C++14
0 / 110
28 ms11064 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[3][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++){ if (cond != 2) res[i] = min(res[i],a[i]); for (ll j = 0;j < b.size();j++){ if (i + j == 1) continue; if (cond == 1 && (j == 1 || i == 1)) continue; if (!cond && i == 1){ res[i + j] = min(res[i + j],a[i] + dp[0][id][j]); continue; } if (cond == 2 && !j) continue; res[i + j] = min(res[i + j],a[i] + b[j]); } } return res; } vector<ll> Getmin(vector<ll> a,vector<ll> b){ ll sz = max(a.size(),b.size()); vector<ll> res(sz,inf); for (ll i = 0;i < sz;i++){ if (i < a.size()) res[i] = min(res[i],a[i]); if (i < b.size()) res[i] = min(res[i],b[i]); } 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}; dp[2][u] = {inf,a[u]}; //if (u == 1) out(dp[0][1]); for (auto i : g[u]) if (i != p){ dp[0][u] = Getmin(combine(dp[0][u],mix[i],0,i),combine(dp[2][u],dp[0][i],2,i)); dp[1][u] = combine(dp[1][u],mix[i],1,i); dp[2][u] = combine(dp[2][u],mix[i],2,i); //if (u == 1) out(dp[2][u]); } 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 "tst" 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}); } sort(v.begin(),v.end()); ll now = 0,sz = v.size(),mx = 0; for (ll i = 1;i <= Q;i++){ while(now < sz && v[now].fs <= q[i].fs) mx = max(mx,v[now].sc),now++; if (!now) ans[q[i].sc] = 0; else ans[q[i].sc] = mx; } 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:24: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]
   24 |     for (ll i = 0;i < a.size();i++){
      |                   ~~^~~~~~~~~~
dzumbus.cpp:26: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]
   26 |         for (ll j = 0;j < b.size();j++){
      |                       ~~^~~~~~~~~~
dzumbus.cpp: In function 'std::vector<long long int> Getmin(std::vector<long long int>, std::vector<long long int>)':
dzumbus.cpp:44:15: 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]
   44 |         if (i < a.size()) res[i] = min(res[i],a[i]);
      |             ~~^~~~~~~~~~
dzumbus.cpp:45:15: 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]
   45 |         if (i < b.size()) res[i] = min(res[i],b[i]);
      |             ~~^~~~~~~~~~
dzumbus.cpp: In function 'void DFS(long long int, long long int)':
dzumbus.cpp:60: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]
   60 |     for (ll i = 0;i < dp[0][u].size();i++)
      |                   ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:92: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]
   92 |     for (ll i = 0;i < dp[1][0].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...