Submission #463928

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
463928	2021-08-12T03:42:36 Z	NhatMinh0208	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	423 ms	262148 KB

dango_maker

#ifndef CPL_TEMPLATE
#define CPL_TEMPLATE
/*
	Normie's Template v2.5
	Changes:
    Added warning against using pragmas on USACO.
*/
// Standard library in one include.
#include <bits/stdc++.h>
using namespace std;
 
// ordered_set library.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set(el) tree<el,null_type,less<el>,rb_tree_tag,tree_order_statistics_node_update>
 
// AtCoder library. (Comment out these two lines if you're not submitting in AtCoder.) (Or if you want to use it in other judges, run expander.py first.)

#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <vector>


#include <vector>

namespace atcoder {

namespace internal {

template <class T> struct simple_queue {
    std::vector<T> payload;
    int pos = 0;
    void reserve(int n) { payload.reserve(n); }
    int size() const { return int(payload.size()) - pos; }
    bool empty() const { return pos == int(payload.size()); }
    void push(const T& t) { payload.push_back(t); }
    T& front() { return payload[pos]; }
    void clear() {
        payload.clear();
        pos = 0;
    }
    void pop() { pos++; }
};

}  // namespace internal

}  // namespace atcoder


namespace atcoder {

template <class Cap> struct mf_graph {
  public:
    mf_graph() : _n(0) {}
    explicit mf_graph(int n) : _n(n), g(n) {}

    int add_edge(int from, int to, Cap cap) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        assert(0 <= cap);
        int m = int(pos.size());
        pos.push_back({from, int(g[from].size())});
        int from_id = int(g[from].size());
        int to_id = int(g[to].size());
        if (from == to) to_id++;
        g[from].push_back(_edge{to, to_id, cap});
        g[to].push_back(_edge{from, from_id, 0});
        return m;
    }

    struct edge {
        int from, to;
        Cap cap, flow;
    };

    edge get_edge(int i) {
        int m = int(pos.size());
        assert(0 <= i && i < m);
        auto _e = g[pos[i].first][pos[i].second];
        auto _re = g[_e.to][_e.rev];
        return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
    }
    std::vector<edge> edges() {
        int m = int(pos.size());
        std::vector<edge> result;
        for (int i = 0; i < m; i++) {
            result.push_back(get_edge(i));
        }
        return result;
    }
    void change_edge(int i, Cap new_cap, Cap new_flow) {
        int m = int(pos.size());
        assert(0 <= i && i < m);
        assert(0 <= new_flow && new_flow <= new_cap);
        auto& _e = g[pos[i].first][pos[i].second];
        auto& _re = g[_e.to][_e.rev];
        _e.cap = new_cap - new_flow;
        _re.cap = new_flow;
    }

    Cap flow(int s, int t) {
        return flow(s, t, std::numeric_limits<Cap>::max());
    }
    Cap flow(int s, int t, Cap flow_limit) {
        assert(0 <= s && s < _n);
        assert(0 <= t && t < _n);
        assert(s != t);

        std::vector<int> level(_n), iter(_n);
        internal::simple_queue<int> que;

        auto bfs = [&]() {
            std::fill(level.begin(), level.end(), -1);
            level[s] = 0;
            que.clear();
            que.push(s);
            while (!que.empty()) {
                int v = que.front();
                que.pop();
                for (auto e : g[v]) {
                    if (e.cap == 0 || level[e.to] >= 0) continue;
                    level[e.to] = level[v] + 1;
                    if (e.to == t) return;
                    que.push(e.to);
                }
            }
        };
        auto dfs = [&](auto self, int v, Cap up) {
            if (v == s) return up;
            Cap res = 0;
            int level_v = level[v];
            for (int& i = iter[v]; i < int(g[v].size()); i++) {
                _edge& e = g[v][i];
                if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
                Cap d =
                    self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
                if (d <= 0) continue;
                g[v][i].cap += d;
                g[e.to][e.rev].cap -= d;
                res += d;
                if (res == up) return res;
            }
            level[v] = _n;
            return res;
        };

        Cap flow = 0;
        while (flow < flow_limit) {
            bfs();
            if (level[t] == -1) break;
            std::fill(iter.begin(), iter.end(), 0);
            Cap f = dfs(dfs, t, flow_limit - flow);
            if (!f) break;
            flow += f;
        }
        return flow;
    }

    std::vector<bool> min_cut(int s) {
        std::vector<bool> visited(_n);
        internal::simple_queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            visited[p] = true;
            for (auto e : g[p]) {
                if (e.cap && !visited[e.to]) {
                    visited[e.to] = true;
                    que.push(e.to);
                }
            }
        }
        return visited;
    }

  private:
    int _n;
    struct _edge {
        int to, rev;
        Cap cap;
    };
    std::vector<std::pair<int, int>> pos;
    std::vector<std::vector<_edge>> g;
};

}  // namespace atcoder

using namespace atcoder;

//Pragmas (Comment out these three lines if you're submitting in szkopul or USACO.)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops,tree-vectorize")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 
//File I/O.
#define FILE_IN "cseq.inp"
#define FILE_OUT "cseq.out"
#define ofile freopen(FILE_IN,"r",stdin);freopen(FILE_OUT,"w",stdout)
 
//Fast I/O.
#define fio ios::sync_with_stdio(0);cin.tie(0)
#define nfio cin.tie(0)
#define endl "\n"
 
//Order checking.
#define ord(a,b,c) ((a>=b)and(b>=c))
 
//min/max redefines, so i dont have to resolve annoying compile errors.
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

// Fast min/max assigns to use with AVX.
// Requires g++ 9.2.0.
template<typename T>
__attribute__((always_inline)) void chkmin(T& a, const T& b) {
    a=(a<b)?a:b;
}

template<typename T>
__attribute__((always_inline)) void chkmax(T& a, const T& b) {
    a=(a>b)?a:b;
}
 
//Constants.
#define MOD (ll(998244353))
#define MAX 300001
#define mag 320
const long double PI=3.14159265358979;
 
//Pairs and 3-pairs.
#define p1 first
#define p2 second.first
#define p3 second.second
#define fi first
#define se second
#define pii(element_type) pair<element_type,element_type>
#define piii(element_type) pair<element_type,pii(element_type)>
 
//Quick power of 2.
#define pow2(x) (ll(1)<<x)
 
//Short for-loops.
#define ff(i,__,___) for(int i=__;i<=___;i++)
#define rr(i,__,___) for(int i=__;i>=___;i--)
 
//Typedefs.
#define bi BigInt
typedef long long ll;
typedef long double ld;
typedef short sh;

// Binpow and stuff
ll BOW(ll a, ll x, ll p)
{
	if (!x) return 1;
	ll res=BOW(a,x/2,p);
	res*=res;
	res%=p;
	if (x%2) res*=a;
	return res%p;
}
ll INV(ll a, ll p)
{
	return BOW(a,p-2,p);
}
//---------END-------//
#endif
vector<int> vec;
int n,m,i,j,k,t,t1,u,v,a,b;
int arr[3001][3001];
vector<int> lmao[3001][3001];

int main()
{
	fio;
    cin>>n>>m;
    char c;
    for (i=1;i<=n;i++) for (j=1;j<=m;j++)
    {
        cin>>c;
        if (c=='R') arr[i][j]=0;
        else if (c=='G') arr[i][j]=1;
        else arr[i][j]=2;
    }
    t=0;
    for (i=1;i<=n;i++) for (j=1;j<=m-2;j++)
    {
        if (arr[i][j]==0 && arr[i][j+1]==1 && arr[i][j+2]==2) 
        {
            t++;
            lmao[i][j].push_back(t);
            lmao[i][j+1].push_back(t);
            lmao[i][j+2].push_back(t);
        }
    }
    t1=t;
    for (i=1;i<=n-2;i++) for (j=1;j<=m;j++)
    {
        if (arr[i][j]==0 && arr[i+1][j]==1 && arr[i+2][j]==2) 
        {
            t++;
            lmao[i][j].push_back(t);
            lmao[i+1][j].push_back(t);
            lmao[i+2][j].push_back(t);
        }
    }
    mf_graph<int> gr(t+2);
    for (i=1;i<=t1;i++) gr.add_edge(0,i,1);
    for (i=t1+1;i<=t;i++) gr.add_edge(i,t+1,1);
    for (i=1;i<=n;i++) for (j=1;j<=m;j++) if (lmao[i][j].size()==2)
    {
        gr.add_edge(lmao[i][j][0],lmao[i][j][1],1);
    }
    cout<<t-gr.flow(0,t+1);
}
// Normie28

Compilation message

dango_maker.cpp:195: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
  195 | #pragma comment(linker, "/stack:200000000")
      |

Subtask #1
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	113 ms	211688 KB	Output is correct
2	Correct	115 ms	211744 KB	Output is correct
3	Correct	111 ms	211788 KB	Output is correct
4	Correct	121 ms	211772 KB	Output is correct
5	Correct	122 ms	211696 KB	Output is correct
6	Correct	112 ms	211704 KB	Output is correct
7	Correct	115 ms	211816 KB	Output is correct
8	Correct	114 ms	211728 KB	Output is correct
9	Correct	128 ms	211884 KB	Output is correct
10	Correct	112 ms	211732 KB	Output is correct
11	Correct	114 ms	211780 KB	Output is correct
12	Correct	113 ms	211700 KB	Output is correct
13	Correct	113 ms	211696 KB	Output is correct
14	Correct	111 ms	211756 KB	Output is correct
15	Correct	111 ms	211760 KB	Output is correct
16	Correct	122 ms	211816 KB	Output is correct

Subtask #2
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	113 ms	211688 KB	Output is correct
2	Correct	115 ms	211744 KB	Output is correct
3	Correct	111 ms	211788 KB	Output is correct
4	Correct	121 ms	211772 KB	Output is correct
5	Correct	122 ms	211696 KB	Output is correct
6	Correct	112 ms	211704 KB	Output is correct
7	Correct	115 ms	211816 KB	Output is correct
8	Correct	114 ms	211728 KB	Output is correct
9	Correct	128 ms	211884 KB	Output is correct
10	Correct	112 ms	211732 KB	Output is correct
11	Correct	114 ms	211780 KB	Output is correct
12	Correct	113 ms	211700 KB	Output is correct
13	Correct	113 ms	211696 KB	Output is correct
14	Correct	111 ms	211756 KB	Output is correct
15	Correct	111 ms	211760 KB	Output is correct
16	Correct	122 ms	211816 KB	Output is correct
17	Correct	115 ms	211700 KB	Output is correct
18	Correct	115 ms	211780 KB	Output is correct
19	Correct	112 ms	211840 KB	Output is correct
20	Correct	112 ms	211764 KB	Output is correct
21	Correct	112 ms	211884 KB	Output is correct
22	Correct	115 ms	211748 KB	Output is correct
23	Correct	114 ms	211736 KB	Output is correct
24	Correct	121 ms	211800 KB	Output is correct
25	Correct	114 ms	211828 KB	Output is correct
26	Correct	112 ms	211720 KB	Output is correct
27	Correct	119 ms	211768 KB	Output is correct
28	Correct	114 ms	211780 KB	Output is correct
29	Correct	111 ms	211848 KB	Output is correct
30	Correct	114 ms	211868 KB	Output is correct
31	Correct	115 ms	211780 KB	Output is correct
32	Correct	113 ms	211804 KB	Output is correct
33	Correct	111 ms	211776 KB	Output is correct
34	Correct	114 ms	211908 KB	Output is correct
35	Correct	112 ms	211956 KB	Output is correct
36	Correct	112 ms	211792 KB	Output is correct
37	Correct	114 ms	211820 KB	Output is correct
38	Correct	112 ms	211852 KB	Output is correct
39	Correct	116 ms	211728 KB	Output is correct
40	Correct	112 ms	211780 KB	Output is correct
41	Correct	116 ms	211780 KB	Output is correct
42	Correct	114 ms	211796 KB	Output is correct
43	Correct	113 ms	211824 KB	Output is correct
44	Correct	112 ms	211740 KB	Output is correct
45	Correct	113 ms	211740 KB	Output is correct
46	Correct	114 ms	211980 KB	Output is correct
47	Correct	112 ms	211836 KB	Output is correct
48	Correct	112 ms	211748 KB	Output is correct
49	Correct	115 ms	211896 KB	Output is correct
50	Correct	114 ms	211756 KB	Output is correct
51	Correct	115 ms	211860 KB	Output is correct
52	Correct	132 ms	211780 KB	Output is correct
53	Correct	115 ms	211820 KB	Output is correct

Subtask #3
0 / 67.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	113 ms	211688 KB	Output is correct
2	Correct	115 ms	211744 KB	Output is correct
3	Correct	111 ms	211788 KB	Output is correct
4	Correct	121 ms	211772 KB	Output is correct
5	Correct	122 ms	211696 KB	Output is correct
6	Correct	112 ms	211704 KB	Output is correct
7	Correct	115 ms	211816 KB	Output is correct
8	Correct	114 ms	211728 KB	Output is correct
9	Correct	128 ms	211884 KB	Output is correct
10	Correct	112 ms	211732 KB	Output is correct
11	Correct	114 ms	211780 KB	Output is correct
12	Correct	113 ms	211700 KB	Output is correct
13	Correct	113 ms	211696 KB	Output is correct
14	Correct	111 ms	211756 KB	Output is correct
15	Correct	111 ms	211760 KB	Output is correct
16	Correct	122 ms	211816 KB	Output is correct
17	Correct	115 ms	211700 KB	Output is correct
18	Correct	115 ms	211780 KB	Output is correct
19	Correct	112 ms	211840 KB	Output is correct
20	Correct	112 ms	211764 KB	Output is correct
21	Correct	112 ms	211884 KB	Output is correct
22	Correct	115 ms	211748 KB	Output is correct
23	Correct	114 ms	211736 KB	Output is correct
24	Correct	121 ms	211800 KB	Output is correct
25	Correct	114 ms	211828 KB	Output is correct
26	Correct	112 ms	211720 KB	Output is correct
27	Correct	119 ms	211768 KB	Output is correct
28	Correct	114 ms	211780 KB	Output is correct
29	Correct	111 ms	211848 KB	Output is correct
30	Correct	114 ms	211868 KB	Output is correct
31	Correct	115 ms	211780 KB	Output is correct
32	Correct	113 ms	211804 KB	Output is correct
33	Correct	111 ms	211776 KB	Output is correct
34	Correct	114 ms	211908 KB	Output is correct
35	Correct	112 ms	211956 KB	Output is correct
36	Correct	112 ms	211792 KB	Output is correct
37	Correct	114 ms	211820 KB	Output is correct
38	Correct	112 ms	211852 KB	Output is correct
39	Correct	116 ms	211728 KB	Output is correct
40	Correct	112 ms	211780 KB	Output is correct
41	Correct	116 ms	211780 KB	Output is correct
42	Correct	114 ms	211796 KB	Output is correct
43	Correct	113 ms	211824 KB	Output is correct
44	Correct	112 ms	211740 KB	Output is correct
45	Correct	113 ms	211740 KB	Output is correct
46	Correct	114 ms	211980 KB	Output is correct
47	Correct	112 ms	211836 KB	Output is correct
48	Correct	112 ms	211748 KB	Output is correct
49	Correct	115 ms	211896 KB	Output is correct
50	Correct	114 ms	211756 KB	Output is correct
51	Correct	115 ms	211860 KB	Output is correct
52	Correct	132 ms	211780 KB	Output is correct
53	Correct	115 ms	211820 KB	Output is correct
54	Correct	112 ms	211836 KB	Output is correct
55	Correct	121 ms	223872 KB	Output is correct
56	Correct	117 ms	212312 KB	Output is correct
57	Correct	121 ms	220432 KB	Output is correct
58	Correct	202 ms	235476 KB	Output is correct
59	Runtime error	423 ms	262148 KB	Execution killed with signal 9
60	Halted	0 ms	0 KB	-

Submission #463928

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 67.0

Subtask #1
13.0 / 13.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 67.0