Submission #736142

#TimeUsernameProblemLanguageResultExecution timeMemory
736142marvinthangDžumbus (COCI19_dzumbus)C++17
110 / 110
54 ms25548 KiB
/****************************** * 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 (stderr)

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);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...