Submission #1275064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275064		G_thang_dizz_lenhi	Domino (COCI15_domino)	C++17	30 / 160	727 ms	260600 KiB

domino

#include<bits/stdc++.h>
typedef long long ii;
typedef long long ll;

using namespace std;

const string name = "";
const ii MOD = 1e9 + 7;
const ii N = 2000 + 10;
const ii INF = 1e9 + 237;

ii n, k;
ii a[N][N], nick[N][N];
ii sum = 0;



void INP(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if (fopen((name + ".inp").c_str(),"r")){
        freopen((name + ".inp").c_str(),"r",stdin);
        freopen((name + ".out").c_str(),"w",stdout);
    }

    cin >> n >> k;
    ii cnt = 0;
    for (ii i = 1;i <= n;i++){
        for (ii j = 1;j <= n;j++){
            cin >> a[i][j];
            nick[i][j] = ++cnt;
            sum += a[i][j];
        }
    }
}

struct MCMF{
    struct Edge{
        ii u, v, capa, cost, flow;

        Edge(ii _u, ii _v, ii _capa, ii _cost){
            u = _u; v = _v; capa = _capa; cost = _cost; flow = 0;
        }

        ii res(){
            return capa - flow;
        }
    };

    ii Size, s, t;
    vector<ii> par, inq, dist;
    vector<vector<ii>> e;
    vector<Edge> edge;

    MCMF(ii Size) : Size(Size) {
        s = 0, t = Size - 1;
        par.resize(Size);
        inq.resize(Size);
        dist.resize(Size);
        e.resize(Size);
    }

    void AddEdge(ii u, ii v, ii capa, ii cost){
        e[u].push_back(edge.size());
        edge.push_back({u, v, capa, cost});
        e[v].push_back(edge.size());
        edge.push_back({v, u, 0, -cost});
    }

    bool find_PATH(){
        fill(dist.begin(), dist.end(), MOD);
        fill(inq.begin(), inq.end(), 0);
        queue<ii> q; q.push(s);
        ii u, v;
        dist[s] = 0;
        while(!q.empty()){
            u = q.front(); q.pop();
            inq[u] = false;
            for (ii dir : e[u]){
                v = edge[dir].v;
                if (dist[v] > dist[u] + edge[dir].cost && edge[dir].res() > 0){
                    dist[v] = dist[u] + edge[dir].cost;
                    par[v] = dir;
                    if (!inq[v]){
                        inq[v] = true;
                        q.push(v);
                    }
                }
            }
        }
        return dist[t] != MOD;
    }

    ll Mincost(ii k){
        ll res = 0;
        cerr << k << endl;
        while(k-- && find_PATH()){
            for (ii u = t;u != s;u = edge[par[u]].u){
//                cerr << u << " ";
                edge[par[u]].flow++;
                edge[par[u] ^ 1].flow--;
            }
//            cerr << s << endl;
//            cerr << dist[t] << endl;
            res += dist[t];
        }
        return res;
    }
};

ii dx[] = {0, 0, 1, -1},
   dy[] = {1, -1, 0, 0};


int main(){
    INP();
    priority_queue<pair<ii, pair<ii, ii>>> pq;
    ii nx, ny;
    for (ii i = 1;i <= n;i++){
        for (ii j = 1;j <= n;j++){
            if ((i + j) & 1){
                for (ii dir = 0;dir < 4;dir++){
                    nx = i + dx[dir];
                    ny = j + dy[dir];
                    if (1 <= nx && nx <= n && 1 <= ny && ny <= n){
                        pq.push({a[i][j] + a[nx][ny], {nick[i][j], nick[nx][ny]}});
                    }
                }
            }
        }
    }

    map<ii, ii> mp;
    map<ii, bool> mark;
    ii cnt = 10;
    ii len, u, v, tmp = 0;
    MCMF NET(202);
    while(!pq.empty() && cnt--){
        tie(u, v) = pq.top().second;
        len = pq.top().first;
        pq.pop();
        if (mp[u] == 0) mp[u] = ++tmp;
        if (mp[v] == 0) mp[v] = ++tmp;
        if (!mark[mp[u]]){
            NET.AddEdge(0, mp[u], 1, 0);
            mark[mp[u]] = true;
        }
        if (!mark[mp[v]]){
            NET.AddEdge(mp[v], NET.t, 1, 0);
            mark[mp[v]] = true;
        }
        NET.AddEdge(mp[u], mp[v], 1, -len);
//        cerr << u << " " << v << "-->" << mp[u] << " " << mp[v] << endl;
//        cerr << len << endl;
    }

    cout << sum + NET.Mincost(k);
    return 0;
}

//NGT 1600-2000 cf
//1/200 hard quests

Compilation message (stderr)

domino.cpp: In function 'void INP()':
domino.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen((name + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
domino.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen((name + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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