Submission #447356

#TimeUsernameProblemLanguageResultExecution timeMemory
447356XBoRickieKronican (COCI16_kronican)C++11
0 / 100
3 ms588 KiB
#include <bits/stdc++.h> using namespace std; // Typedef typedef long double ld; typedef long long int int64; typedef unsigned long long int uint64; typedef std::pair<int, int> PII; typedef std::pair<int64, int64> PLL; typedef std::vector<int> VI; typedef std::vector<long long> VLL; // Define For-loop #define FOR(i, j, k, in) for (int i = (j); i < (k) ; i += (in)) #define FORW(i, j, k, in) for (int i = (j); i <= (k); i += (in)) #define RFOR(i, j, k, in) for (int i = (j); i >= (k); i -= (in)) // Define Data structure func #define all(cont) cont.begin(), cont.end() #define rall(cont) cont.rbegin(), cont.rend() #define sz(cont) int((cont).size()) #define pb push_back #define mp make_pair #define fi first #define se second // Define number #define IINF 0x3f3f3f3f #define LLINF 1000111000111000111LL #define PI 3.1415926535897932384626433832795 // Other #define lend '\n' #define hardio(name) freopen(name".inp","r",stdin), freopen(name".out","w",stdout); void FastIO() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); cin.exceptions(cin.failbit); srand(time(NULL)); } const int MOD = 1e9 + 7, MOD2 = 1e9 + 9; // ====================================================================== struct Edge { int a = 0, b = 0, w = IINF; Edge() {}; Edge(int a_, int b_, int w_): a(a_), b(b_), w(w_) {}; }; struct Directed_MT { int n; vector<Edge> e; int in[26], vis[26], par[26], id[26]; void init(int n_) { n = max(n_, 0); e.clear(); } void addEdge(int a, int b, int w) { e.pb(Edge(a, b, w)); } int calc(int root) { int ans = 0; while (1) { FOR(i, 0, n, 1) in[i] = IINF; FOR(i, 0, sz(e), 1) { int u = e[i].a, v = e[i].b; if (e[i].w < in[v] && u != v) { in[v] = e[i].w; par[v] = u; } } FOR(i, 0, n, 1) { if (i == root) continue; // pass out the root if (in[i] == IINF) return -1; // not enough edge } int cnt = 0; memset(vis, -1, sizeof vis); memset(id, -1, sizeof id); in[root] = 0; FOR(i, 0, n, 1) { ans += in[i]; int t = i; while (vis[t] != i && id[t] == -1 && t != root) { vis[t] = i; t = par[t]; } if (t != root && id[t] == -1) { for(int s = par[t]; s != t; s = par[s]) id[s] = cnt; id[t] = cnt++; } } if (cnt == 0) break; FOR(i, 0, n, 1) if (id[i] == -1) id[i] = cnt++; FOR(i, 0, sz(e), 1) { int v = e[i].b; e[i].b = id[e[i].b]; e[i].a = id[e[i].a]; if (e[i].a != e[i].b) { e[i].w -= in[v]; } } n = cnt; root = id[root]; } return ans; } } T; int n, k, a[36] = {}; int c[36][36] = {}; int calc() { T.init(n + 1); FORW(i, 1, n, 1) { if (a[i] == 1) T.addEdge(n, i - 1, 0); else { FORW(j, 1, n, 1) if (i != j) T.addEdge(j - 1, i - 1, c[i][j]); } } return T.calc(n); } int main(int argc, char* argv[]) { FastIO(); #ifndef ONLINE_JUDGE hardio("input"); #endif cin >> n >> k; FORW(i, 1, n, 1) FORW(j, 1, n, 1) cin >> c[i][j]; FORW(i, 1, n - k, 1) a[i] = 0; // bottle we will get rid FORW(i, n - k + 1, n, 1) a[i] = 1; // bottle we will keep int ans = IINF; do { ans = min(ans, calc()); } while (next_permutation(a + 1, a + 1 + n)); cout << ans << endl; return 0; }

Compilation message (stderr)

kronican.cpp: In function 'int main(int, char**)':
kronican.cpp:29:43: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 | #define hardio(name)               freopen(name".inp","r",stdin), freopen(name".out","w",stdout);
      |                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
kronican.cpp:120:5: note: in expansion of macro 'hardio'
  120 |     hardio("input");
      |     ^~~~~~
kronican.cpp:29:74: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 | #define hardio(name)               freopen(name".inp","r",stdin), freopen(name".out","w",stdout);
      |                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
kronican.cpp:120:5: note: in expansion of macro 'hardio'
  120 |     hardio("input");
      |     ^~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...