oj.uz

Submission #1101845

# Submission time Handle Problem Language Result Execution time Memory
1101845 2024-10-17T03:06:44 Z phamducminh Selotejp (COCI20_selotejp) C++17
110 / 110
 10 ms 2796 KB 
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
#include <random>
#include <sstream>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
// #pragma GCC optimize("Ofast","inline","no-stack-protector")


using namespace std;

#define file(name) freopen(name".inp","r",stdin);\
                    freopen(name".out","w",stdout);
#define TIME (1.0*clock()/CLOCKS_PER_SEC)
#define all(a) a.begin(),a.end()
#define all1(a) a+1,a+n+1
#define ll long long

const long long INF=1e18;
const long long MOD=1e9+7;
const long long MODD=998244353; // 998244353
const int maxN=1e6+9;
const short LOG=20;


//------------------------



void solve();
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);


    // file("boat");



    int t;

    // cin >> t;

    t=1;

    while (t--){
        solve();
    }


    return 0;
}

/// -------------- PROBLEM SOLUION --------------------


int n,m;
char a[1009][209];

struct FlowEdge {
    int v, u;
    long long cap, flow = 0;
    FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
};

struct Dinic {
    const long long flow_inf = 1e18;
    vector<FlowEdge> dscanh;
    vector<vector<int>> adj;
    int n, m = 0;
    int s, t;
    vector<int> level, ptr;
    queue<int> q;

    Dinic(int n, int s, int t) : n(n), s(s), t(t) {
        adj.resize(n);
        level.resize(n);
        ptr.resize(n);
    }

    void add_edge(int v, int u, long long cap) {
        dscanh.emplace_back(v, u, cap);
        dscanh.emplace_back(u, v, 0);
        adj[v].push_back(m);
        adj[u].push_back(m + 1);
        m += 2;
    }

    bool bfs() {
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int id : adj[v]) {
                if (dscanh[id].cap - dscanh[id].flow < 1)
                    continue;
                if (level[dscanh[id].u] != -1)
                    continue;
                level[dscanh[id].u] = level[v] + 1;
                q.push(dscanh[id].u);
            }
        }
        return level[t] != -1;
    }

    long long dfs(int v, long long pushed) {
        if (pushed == 0)
            return 0;
        if (v == t)
            return pushed;
        for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
            int id = adj[v][cid];
            int u = dscanh[id].u;
            if (level[v] + 1 != level[u] || dscanh[id].cap - dscanh[id].flow < 1)
                continue;
            long long tr = dfs(u, min(pushed, dscanh[id].cap - dscanh[id].flow));
            if (tr == 0)
                continue;
            dscanh[id].flow += tr;
            dscanh[id ^ 1].flow -= tr;
            return tr;
        }
        return 0;
    }

    long long flow() {
        long long f = 0;
        while (true) {
            fill(level.begin(), level.end(), -1);
            level[s] = 0;
            q.push(s);
            if (!bfs())
                break;
            fill(ptr.begin(), ptr.end(), 0);
            while (long long pushed = dfs(s, flow_inf)) {
                f += pushed;
            }
        }
        return f;
    }
};

// Dinic A;


int id(int i, int j){
    return (i-1)*m+j;
}

void solve() {

    
    cin >> n >> m;

    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++) {
            cin >> a[i][j];
        }
    }


    Dinic A(n*m+2,0,n*m+1);
    
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            if (a[i][j]=='#') {
                if (a[i][j-1]=='#') A.add_edge(id(i,j),id(i,j-1),1);
                else A.add_edge(id(i,j),A.t,1);
                if (a[i-1][j]=='#') A.add_edge(id(i-1,j),id(i,j),1);
                else A.add_edge(A.s,id(i,j),1);
            }
        }
    }
    cout << A.flow() << "\n";
}

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1352 KB Output is correct
4 Correct 2 ms 1344 KB Output is correct
5 Correct 2 ms 1400 KB Output is correct
6 Correct 3 ms 1400 KB Output is correct
7 Correct 3 ms 1404 KB Output is correct
8 Correct 2 ms 1108 KB Output is correct
9 Correct 3 ms 1348 KB Output is correct
10 Correct 3 ms 1908 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 504 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1352 KB Output is correct
4 Correct 2 ms 1344 KB Output is correct
5 Correct 2 ms 1400 KB Output is correct
6 Correct 3 ms 1400 KB Output is correct
7 Correct 3 ms 1404 KB Output is correct
8 Correct 2 ms 1108 KB Output is correct
9 Correct 3 ms 1348 KB Output is correct
10 Correct 3 ms 1908 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 504 KB Output is correct
19 Correct 2 ms 1344 KB Output is correct
20 Correct 3 ms 1400 KB Output is correct
21 Correct 4 ms 1916 KB Output is correct
22 Correct 1 ms 848 KB Output is correct
23 Correct 2 ms 1104 KB Output is correct
24 Correct 3 ms 1340 KB Output is correct
25 Correct 5 ms 1912 KB Output is correct
26 Correct 10 ms 1904 KB Output is correct
27 Correct 8 ms 2540 KB Output is correct
28 Correct 8 ms 2796 KB Output is correct