oj.uz

Submission #736142

# Submission time Handle Problem Language Result Execution time Memory
736142 2023-05-05T09:04:19 Z marvinthang Džumbus (COCI19_dzumbus) C++17
110 / 110
 54 ms 25548 KB 
/******************************
*    author : @marvinthang    *
*    date : 09 / 02 / 2022    *
******************************/

#include <bits/stdc++.h>

using namespace std;

#define  superspeed  ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
#define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }

template <class U, class V> ostream & operator << (ostream& out, const pair<U, V> &p) { return out << '(' << p.first << ", " << p.second << ')'; }
template <class T> ostream & operator << (ostream &out, const vector<T> &vt) { out << '{'; for (size_t i = 0; i + 1 < vt.size(); i++) out << vt[i] << ", "; if (!vt.empty()) out << vt.back(); return out << '}'; }

const 		int MOD = 1e9 + 7;
const     double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const     int dir[] = {0, 1, 0, -1, 0}; // {0, 1, 1, -1, -1, 1, 0, -1, 0};
const  long long oo = 1e15;
const       int MAX = 1003;

int N, M, Q, treeSize[MAX];
long long D[MAX], F[MAX][MAX][2], G[MAX][MAX][2];
int res[200005];
pair <int, int> queries[200005];
vector <int> adj[MAX];

inline void minimize(long long &a, long long b) { if (a > b) a = b; }

void calc(int u, int par = 0) {
	if (u) for (int &v: adj[u]) if (v != par) calc(v, u);

	treeSize[u] = 1;
	for (int i = 1; i <= (int) adj[u].size(); ++i) {
		int v = adj[u][i - 1];
		if (v == par) {
			for (int j = 0; j <= treeSize[u]; ++j) {
				G[i][j][0] = G[i - 1][j][0];
				G[i][j][1] = G[i - 1][j][1];
			}
			continue;
		}
		for (int j = 0; j <= treeSize[u] + treeSize[v]; ++j) G[i][j][0] = G[i][j][1] = oo;

		for (int a = 0; a <= treeSize[u]; ++a) {
			for (int b = 0; b <= treeSize[v]; ++b) {
				minimize(G[i][a + b][0], G[i - 1][a][0] + min(F[v][b][0], F[v][b][1]));
				if (a) {
					minimize(G[i][a + b][1], G[i - 1][a - 1][0] + D[u] + F[v][b][1]);
					if (b) minimize(G[i][a + b][1], G[i - 1][a - 1][0] + D[u] + F[v][b - 1][0] + D[v]);
				}

				minimize(G[i][a + b][1], G[i - 1][a][1] + min(F[v][b][0], F[v][b][1]));

				if (b) minimize(G[i][a + b][1], G[i - 1][a][1] + F[v][b - 1][0] + D[v]);
			}
		}

		treeSize[u] += treeSize[v];
	}

	for (int i = 0; i <= treeSize[u]; ++i) {
		F[u][i][0] = G[(int) adj[u].size()][i][0];
		F[u][i][1] = G[(int) adj[u].size()][i][1];
	}
}

int main(void) {
    superspeed;
    file("coci1920_r1_dzumbus");
    scanf("%d%d", &N, &M);
    D[0] = oo;
    for (int i = 1; i <= N; ++i) scanf("%lld", D + i);
    while (M--) {
    	int u, v; scanf("%d%d", &u, &v);
    	adj[u].push_back(v);
    	adj[v].push_back(u);
    }

    memset(F, -1, sizeof(F));
	for (int i = 0; i <= N; ++i) G[0][i][0] = G[0][i][1] = oo;
	G[0][0][0] = 0;

    for (int i = 1; i <= N; ++i) {
    	if (F[i][0][0] == -1) {
    		calc(i);
    		adj[0].push_back(i);
    	}
    }
    calc(0);
	for (int i = N; i >= 0; --i) minimize(F[0][i][0], F[0][i + 1][0]);

    scanf("%d", &Q);
    for (int i = 1; i <= Q; ++i) {
    	scanf("%d", &queries[i].first);
    	queries[i].second = i;
    }
    sort(queries + 1, queries + 1 + Q);
    int cur = 0;
    for (int i = 1; i <= Q; ++i) {
    	while (cur < N && F[0][cur + 1][0] <= queries[i].first) ++cur;
    	res[queries[i].second] = cur;
    }
    for (int i = 1; i <= Q; ++i) printf("%d\n", res[i]);
    return 0;
}

Compilation message

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:11:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:70:5: note: in expansion of macro 'file'
   70 |     file("coci1920_r1_dzumbus");
      |     ^~~~
dzumbus.cpp:11:95: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                       ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:70:5: note: in expansion of macro 'file'
   70 |     file("coci1920_r1_dzumbus");
      |     ^~~~
dzumbus.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     scanf("%d%d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~
dzumbus.cpp:73:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     for (int i = 1; i <= N; ++i) scanf("%lld", D + i);
      |                                  ~~~~~^~~~~~~~~~~~~~~
dzumbus.cpp:75:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |      int u, v; scanf("%d%d", &u, &v);
      |                ~~~~~^~~~~~~~~~~~~~~~
dzumbus.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     scanf("%d", &Q);
      |     ~~~~~^~~~~~~~~~
dzumbus.cpp:95:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |      scanf("%d", &queries[i].first);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16340 KB Output is correct
2 Correct 10 ms 16340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16340 KB Output is correct
2 Correct 10 ms 16340 KB Output is correct
3 Correct 47 ms 20752 KB Output is correct
4 Correct 54 ms 21368 KB Output is correct
5 Correct 49 ms 20968 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 20460 KB Output is correct
2 Correct 45 ms 20388 KB Output is correct
3 Correct 42 ms 20960 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16340 KB Output is correct
2 Correct 10 ms 16340 KB Output is correct
3 Correct 47 ms 20752 KB Output is correct
4 Correct 54 ms 21368 KB Output is correct
5 Correct 49 ms 20968 KB Output is correct
6 Correct 46 ms 20460 KB Output is correct
7 Correct 45 ms 20388 KB Output is correct
8 Correct 42 ms 20960 KB Output is correct
9 Correct 45 ms 20896 KB Output is correct
10 Correct 51 ms 23488 KB Output is correct
11 Correct 52 ms 25548 KB Output is correct