oj.uz

Submission #441976

# Submission time Handle Problem Language Result Execution time Memory
441976 2021-07-06T15:52:58 Z Yomapeed Džumbus (COCI19_dzumbus) C++17
50 / 110
 1000 ms 19072 KB 
#include<bits/stdc++.h>
#define pi 3.141592653589793238
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999 
#define pb push_back
#define ff first
#define ss second
 
#define mt make_tuple
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
 
 
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const int N = 1e3 + 5;
ll dp[N][N][2];
void chmin(ll &a, ll b){
	a = min(a, b);
} 
int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	fast;
	ll T = 1;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			for(int k = 0; k < 2; k++){
				dp[i][j][k] = INF;
			}
		}
	}
	//cin >> T;
	while (T--) {
		ll n, m;
		cin >> n >> m;
		
		vector<ll> c(n + 1);
		for(int i = 1; i <= n; i++){
			cin >> c[i];
		}
		vector<vector<ll>> adj(n + 1);
		for(int i = 1; i <= m; i++){
			ll a, b;
			cin >> a >> b;
			adj[a].pb(b);
			adj[b].pb(a);
		}
		ll g = -1;
		for(int i = 1; i <= n; i++){
			if((int)adj[i].size() == 1){
				g = i;
				break;
			}
		}
		assert(g != -1);
		vector<ll> v;
		v.pb(g);
		set<ll> st;
		st.insert(g);
		ll p = -1;
		vector<bool> vis(n + 1);
		vis[g] = 1;
		while((int)v.size() != n){
			
			for(auto u : adj[g]){
				if(!vis[u]){
					v.pb(u);
					st.insert(u);
					p = g;
					g = u;
					vis[u] = true;
				}
			}
		}
		//cout << st.size() << endl;
		assert(st.size() == n);
		dp[0][0][0] = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j <= n; j++){
				chmin(dp[i + 1][j][0], dp[i][j][0]);
				chmin(dp[i + 1][j][0], dp[i][j][1]);
				
				chmin(dp[i + 1][j + 1][1], dp[i][j][1] + c[v[i]]);
				
				if(i >= 1){
					chmin(dp[i + 1][j + 2][1], dp[i][j][0] + c[v[i - 1]] + c[v[i]]);
				}
			}
		}
		
		ll q;
		cin >> q;
		while(q--){
			ll s;
			cin >> s;
			ll ans = 0;
			for(int i = n; i >= 0; i--){
				
				if(dp[n][i][0] <= s || dp[n][i][1] <= s){
					ans = i;
					break;
				}
			}
			assert(ans != 1);
			cout << ans << "\n";
		}
	}
	return 0;
}

Compilation message

dzumbus.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
dzumbus.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
                 from dzumbus.cpp:16:
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:85:20: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   85 |   assert(st.size() == n);
      |          ~~~~~~~~~~^~~~
dzumbus.cpp:69:6: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   69 |   ll p = -1;
      |      ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16204 KB Output is correct
2 Correct 15 ms 16204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16204 KB Output is correct
2 Correct 15 ms 16204 KB Output is correct
3 Correct 92 ms 18388 KB Output is correct
4 Correct 94 ms 19072 KB Output is correct
5 Correct 273 ms 18584 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 16076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16204 KB Output is correct
2 Correct 15 ms 16204 KB Output is correct
3 Correct 92 ms 18388 KB Output is correct
4 Correct 94 ms 19072 KB Output is correct
5 Correct 273 ms 18584 KB Output is correct
6 Execution timed out 1097 ms 16076 KB Time limit exceeded
7 Halted 0 ms 0 KB -