Submission #676293

#	Time	Username	Problem	Language	Result	Execution time	Memory
676293		Do_you_copy	Domino (COCI15_domino)	C++17	110 / 160	1056 ms	524288 KiB

domino

//Then
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 2e3 + 10;
//const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int n, k;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
struct TEdge{
    int u, v, c, w;
};
vector <TEdge> S;
vector <int> adj[maxN * maxN];
bitset <int(4e6 + 10)> inqueue;
int trace[maxN * maxN];
int d[maxN * maxN];
int conv(int x, int y){
    if (x > n || y > n || !x || !y) return 0;
    return (x - 1) * n + y;
}

void add_edge(int u, int v, int c, int w){
    w = -w;
    adj[u].pb(S.size());
    S.pb({u, v, c, w});
    adj[v].pb(S.size());
    S.pb({v, u, 0, -w});
}

void MCMF(){
    fill(d, d + n * n + 2, inf);
    d[0] = 0;
    queue <int> Q;
    Q.push(0);
    while (!Q.empty()){
        int u = Q.front();
        inqueue[u] = 0;
        Q.pop();
        for (int i: adj[u]){
            int v = S[i].v, c = S[i].c, w = S[i].w;
            if (!c || d[v] <= d[u] + w) continue;
            d[v] = d[u] + w;
            trace[v] = i;
            if (!inqueue[v]){
                inqueue[v] = 1;
                Q.push(v);
            }
        }
    }
}

void Init(){
    cin >> n >> k;
    int sum = 0;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j){
            cin >> d[conv(i, j)];
        }
    }
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j){
            sum += d[conv(i, j)];
            if ((i + j) & 1){
                add_edge(conv(i, j), n * n + 1, 1, 0);
                continue;
            }
            add_edge(0, conv(i, j), 1, 0);
            for (int k = 0; k < 4; ++k){
                int v = conv(i + dx[k], j + dy[k]);
                if (!v) continue;
                add_edge(conv(i, j), v, 1, d[conv(i, j)] + d[v]);
            }
        }
    }
    while (k--){
        MCMF();
        int v = n * n + 1;
        sum += d[v];
        while (v){
            int i = trace[v];
            S[i].c ^= 1;
            S[i ^ 1].c ^= 1;
            v = S[i].u;
        }
    }
    cout << sum;
}

#define debug
#define taskname "test"
signed main(){
    faster
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    int tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
        timeout.close();
        #ifndef debug
        cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
        #endif // debug
    }
}

Compilation message (stderr)

domino.cpp: In function 'int main()':
domino.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
domino.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 0 / 10
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10
• Subtask 16: 0 / 10