Submission #330169

#	Time	Username	Problem	Language	Result	Execution time	Memory
330169		2qbingxuan	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	333 ms	262148 KiB

dango_maker

//   __________________
//  | ________________ |
//  ||          ____  ||
//  ||   /\    |      ||
//  ||  /__\   |      ||
//  || /    \  |____  ||
//  ||________________||
//  |__________________|
//  \###################\
//   \###################\
//    \        ____       \
//     \_______\___\_______\
// An AC a day keeps the doctor away.
 
#ifdef local
#include <bits/extc++.h>
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(args...) qqbx(#args, args)
using ost = std::ostream;
#define DESTL(STL, BEG, END, OUT) \
    template <typename ...T> ost& operator<<(ost &O, std::STL<T...> v) { int f=0; for(auto x: v) O << (f++ ? ", " : BEG) << OUT; return O << END; }
DESTL(deque, "[", "]", x); DESTL(vector, "[", "]", x);
DESTL(set, "{", "}", x); DESTL(multiset, "{", "}", x); DESTL(unordered_set, "{", "}", x);
DESTL(map , "{", "}", x.first << ":" << x.second); DESTL(unordered_map , "{", "}", x.first << ":" << x.second);
template <typename U, typename V> ost& operator<<(ost &O, std::pair<U,V> p) { return O << '(' << p.first << ',' << p.second << ')'; }
template <typename T, size_t N> ost& operator<<(ost &O, std::array<T,N> a) { int f=0; for(T x: a) O << (f++ ? ", " : "[") << x; return O << "]"; }
template <typename T, size_t ...I> ost& prtuple(ost &O, T t, std::index_sequence<I...>) { return (..., (O << (I ? ", " : "(") << std::get<I>(t))), O << ")"; }
template <typename ...T> ost& operator<<(ost &O, std::tuple<T...> t) { return prtuple(O, t, std::make_index_sequence<sizeof...(T)>()); }
template <typename ...T> void qqbx(const char *s, T ...args) {
    int cnt = sizeof...(T);
    (std::cerr << "\033[1;32m(" << s << ") = (" , ... , (std::cerr << args << (--cnt ? ", " : ")\033[0m\n")));
}
#else
#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/extc++.h>
#include <bits/stdc++.h>
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define get_pos(v,x) int(lower_bound(begin(v),end(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define pb emplace_back
#define ff first
#define ss second
#define mem(v,x) memset(v,x,sizeof v)
 
using namespace std;
using namespace __gnu_pbds;
typedef int64_t ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
template <typename T> using max_heap = std::priority_queue<T,vector<T>,less<T> >;
template <typename T> using min_heap = std::priority_queue<T,vector<T>,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
constexpr ld PI = acos(-1), eps = 1e-7;
constexpr ll N = 3025, INF = 1e18, MOD = 1000000007, K = 14699, inf = 1e9;
constexpr inline ll cdiv(ll x, ll m) { return x/m + (x%m ? (x<0) ^ (m>0) : 0); } // ceiling divide
constexpr inline ll modpow(ll e,ll p,ll m=MOD) { ll r=1; for(e%=m;p;p>>=1,e=e*e%m) if(p&1) r=r*e%m; return r; }

struct BPT {
    vector<int> g[N*N];
    bool vis[N*N];
    int mx[N*N], my[N*N];
    void addEdge(int a, int b) {
        g[a].pb(b);
    }
    void init(int X, int Y) {
        for(int i = 1; i <= X; i++) g[i].clear();
        for(int i = 1; i <= X; i++) mx[i] = 0;
        for(int i = 1; i <= Y; i++) my[i] = 0;
    }
    bool dfs(int i) {
        if(vis[i]) return false;
        vis[i] = true;
        for(int j: g[i]) if(!my[j] || dfs(my[j])) {
            my[j] = i;
            mx[i] = j;
            return true;
        }
        return false;
    }
    int solve(int n) {
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) vis[j] = false;
            if(dfs(i)) ++ans;
        }
        return ans;
    }
} g;
int hori[N][N], vert[N][N];
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<string> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];
    int idx = 0, idy = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j+3 <= m; j++) {
            if(v[i].substr(j, 3) == "RGW") {
                hori[i][j] = ++idx;
            }
        }
    }
    for(int j = 0; j < m; j++) {
        for(int i = 0; i+3 <= n; i++) {
            string pat = v[i].substr(j, 1) + v[i+1].substr(j, 1) + v[i+2].substr(j, 1);
            if(pat == "RGW") {
                vert[i][j] = ++idy;
            }
        }
    }
    g.init(idx, idy);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(hori[i][j]) {
                for(int c: {0, 1, 2}) {
                    if(i-c >= 0 && j+c < m && vert[i-c][j+c])
                        g.addEdge(hori[i][j], vert[i-c][j+c]);
                }
            }
        }
    }
    cout << idx+idy - g.solve(idx) << '\n';
}

Compilation message (stderr)

dango_maker.cpp:9:1: warning: multi-line comment [-Wcomment]
    9 | //  \###################\
      | ^
dango_maker.cpp:35: warning: ignoring #pragma loop_opt  [-Wunknown-pragmas]
   35 | #pragma loop_opt(on)
      |

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 0 / 67