oj.uz

Submission #676293

# Submission time Handle Problem Language Result Execution time Memory
676293 2022-12-30T07:31:50 Z Do_you_copy Domino (COCI15_domino) C++17
110 / 160
 1056 ms 524288 KB 
//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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 137956 KB Output is correct
2 Correct 131 ms 137836 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 95636 KB Output is correct
2 Correct 45 ms 95624 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 893 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 95144 KB Output is correct
2 Correct 45 ms 95132 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1056 ms 443452 KB Output is correct
2 Correct 1004 ms 443424 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 265932 KB Output is correct
2 Correct 525 ms 266024 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 902 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 95640 KB Output is correct
2 Correct 48 ms 95660 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 933 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 96652 KB Output is correct
2 Correct 50 ms 96652 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 95192 KB Output is correct
2 Correct 54 ms 95140 KB Output is correct

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 943 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 95892 KB Output is correct
2 Correct 47 ms 95900 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 266028 KB Output is correct
2 Correct 694 ms 265976 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 95180 KB Output is correct
2 Correct 46 ms 95128 KB Output is correct

Subtask #16
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 890 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -