Submission #1081078

#TimeUsernameProblemLanguageResultExecution timeMemory
1081078wibulordDžumbus (COCI19_dzumbus)C++14
110 / 110
42 ms19180 KiB
#include <bits/stdc++.h> #define endl '\n' #define ll long long #define fi first #define se second #define pb emplace_back #define ii pair<int, int> #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) #define sz(s) (int)((s).size()) #define all(a) a.begin(), a.end() #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define F0R(i, b) for (int i = 0, _b = (b); i < _b; ++i) #define FORd(i, a, b) for (int i = (a), _b = (b); i >= _b; --i) #define F0Rd(i, b) for (int i = (b)-1; i >= 0; i--) #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " using namespace std; template<typename T1,typename T2> bool ckmax(T1 &x,const T2 &y){if(x<y){x=y; return 1;} return 0;} template<typename T1,typename T2> bool ckmin(T1 &x,const T2 &y){if(y<x){x=y; return 1;} return 0;} const int MOD = (int)1e9 + 7; const int mod = 998244353; const int N = 1e3 + 10, M = 18; const long long INF = (long long)1e18 + 11; /* /\_/\ (= ._.) / >? \>$ */ mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); long long rand(long long l, long long r){ return l + rd() % (r - l + 1); } int n, m, q; int A[N], s[N]; vector<int> adj[N]; long long F[N][N][2], res[N]; void DFS(int u, int p = -1){ s[u] = 1; for(int v : adj[u]) if(v != p) DFS(v, u); } void dfs(int u, int p = -1){ F[u][0][0] = 0; for(int v : adj[u]) if(v != p){ dfs(v, u); FORd(i, s[u], 0) FORd(j, s[v], 0){ F[u][i+j][0] = min(F[u][i+j][0], F[u][i][0] + min(F[v][j][0], F[v][j][1])); F[u][i+j][1] = min(F[u][i+j][1], F[u][i][1] + min(F[v][j][0], F[v][j][1])); if(i+j+1 <= s[u]+s[v]){ F[u][i+j+1][1] = min(F[u][i+j+1][1], F[u][i][0] + F[v][j][1] + A[u]); F[u][i+j+1][1] = min(F[u][i+j+1][1], F[u][i][1] + F[v][j][0] + A[v]); } if(i+j+2 <= s[u]+s[v]) F[u][i+j+2][1] = min(F[u][i+j+2][1], F[u][i][0] + F[v][j][0] + A[u] + A[v]); } s[u] += s[v]; } } void sol(void){ cin >> n >> m; FOR(i, 1, n) cin >> A[i]; FOR(i, 1, m){ int u, v; cin >> u >> v; adj[u].pb(v), adj[v].pb(u); } A[0] = MOD; FOR(i, 1, n) if(s[i] == 0){ DFS(i); adj[i].pb(0), adj[0].pb(i); } FOR(i, 0, n) FOR(j, 0, n) FOR(k, 0, 1) F[i][j][k] = INF; dfs(0); res[n] = F[0][n][0]; for(int i = n-1; i >= 1; i--) res[i] = min(res[i+1], F[0][i][0]); cin >> q; while(q--){ int s; cin >> s; int p = upper_bound(res+1,res+n+1,s) - res - 1; cout << p << '\n'; } } signed main(void){ #define TASK "nhap" if(fopen(TASK".inp", "r")){ freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; // cin >> t; while(t--) sol(); cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n"; }

Compilation message (stderr)

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         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...