Submission #464977

#	Time	Username	Problem	Language	Result	Execution time	Memory
464977		ewirlan	T-Covering (eJOI19_covering)	C++17	0 / 100	42 ms	48688 KiB

covering

//

#define _CTR_SECURE_NO_WARNINGS
#include <iostream>
#include <utility>
#include <vector>
#define x second
#define y first
typedef std::pair <int, int> pun;
typedef long long int ll;
typedef std::vector <std::vector<bool>> tabb;
typedef std::vector <std::vector<int>> tabi;
template <typename T> T in()
{
    T x;
    std::cin >> x;
    return x;
}
enum dir
{
    U, R, D, L, M
};
dir r(dir p)
{
    return dir((p + 1) % M);
}
dir l(dir p)
{
    return dir((p + M - 1) % M);
}
dir b(dir p)
{
    return dir((p + 2) % M);
}
pun s(pun p, dir d)
{
    switch (d)
    {
    case U: return { p.y - 1, p.x };
    case R: return { p.y, p.x + 1 };
    case D: return { p.y + 1, p.x };
    case L: return { p.y, p.x - 1 };
    default: return { -1, -1 };
    }
}
tabb add;
tabi cen;
tabi wart;
int find(int);
void debug()
{
    return;
    std::cerr << "add:\n";
    for (auto i : add)
    {
        for (auto j : i)std::cerr << j;
        std::cerr << '\n';
    }
    std::cerr << "cen:\n";
    for (auto i : cen)
    {
        for (auto j : i)std::cerr << find(j);
        std::cerr << '\n';
    }
}
bool dod(pun c)
{
    if (add[c.y][c.x])return 0;
    return add[c.y][c.x] = 1;
}
bool jes(pun c)
{
    return add[c.y][c.x];
}
int tet(pun c)
{
    if (c.x < 0 || c.x >= add.size() || c.y < 0 || c.y >= add[0].size())return 1;
    return cen[c.y][c.x];
}
int osc(pun c)
{
    return wart[c.y][c.x];
}
bool upd(pun c);
bool set(pun c, dir d)
{
    if (!dod(s(c, d)) || !dod(s(c, l(d))) || !dod(s(c, r(d))))return 0;
    cen[c.y][c.x] = 0;
    for (dir i(U); i < M; i = dir(i + 1))
    {
        pun ps(s(c, i));
        if (!upd(ps))return 0;
        for (dir i(U); i < M; i = dir(i + 1)) if (!upd(s(ps, i)))return 0;
    }
    debug();
    return 1;
}
bool upd(pun c)
{
    if (c.x < 0 || c.x >= add.size() || c.y < 0 || c.y >= add[0].size())return 1;
    if (!cen[c.y][c.x])return 1;
    debug();
    int jak(1);
    for (dir i(U); i < M; i = dir(i + 1))if(jes(s(c, i)))jak = 10*jak + i;
    if (jak == 1)return 1;
    if (jak >= 10 + M)return 0;
    return set(c, b(dir(jak - 10)));
}
bool end()
{
    std::cout << "No\n";
    return 0;
}
constexpr int maxq = 1e6 + 3;
int rep[maxq];
pun rev[maxq];
std::vector <pun> list[maxq];
int find(int w)
{
    if (!rep[w])return w;
    return rep[w] = find(rep[w]);
}
bool uni(int a, int b, dir d)
{
    if (find(a) == find(b))return set(rev[a], d);
    a = find(a);
    b = find(b);
    rep[a] = b;
    return 1;
}
int main()
{
    std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(0);
    int n(in<int>()), m(in<int>());
    add.resize(n + 2);
    for (int i(0); i <= n + 1; ++i)add[i].resize(m + 2, !i || i > n);
    for (int i(0); i <= n + 1; ++i)add[i][0] = add[i][m + 1] = 1;
    cen.resize(n + 2);
    for (int i(0); i <= n + 1; ++i)cen[i].resize(m + 2, 0);
    wart.resize(n + 2);
    for (int i(0); i <= n + 1; ++i)wart[i].resize(m + 1, 0);

    for (int i(1); i <= n; ++i)for (int j(1); j <= m; ++j)std::cin >> wart[i][j];
    int q(in<int>());
    for (int i(1); i <= q; ++i)
    {
        int a(in<int>() + 1), b(in<int>() + 1);
        add[a][b] = cen[a][b] = i;
        rev[i] = { a, b };
    }
    for (int i(1); i <= n; ++i)for (int j(1); j <= m; ++j)if (!upd({ i, j })) return end();
    for (int i(1); i <= n; ++i)for (int j(1); j <= m; ++j)if (cen[i][j])
    {
        if (cen[i - 1][j - 1] || cen[i - 1][j + 1]) { if (!set({ i, j }, D))return end(); }
        else if (cen[i + 1][i + 1] || cen[i + 1][j - 1])if(!set({ i, j }, U))return end();
    }
    for (int i(1); i <= n; ++i)for (int j(1); j <= m; ++j)
        if (cen[i][j]) for (dir d(U); d < M; d = dir(d + 1))if (tet(s(s({ i, j }, d), d)))if(!uni(cen[i][j], tet(s(s({ i, j }, d), d)), d))return end();
    for (int i(1); i <= n; ++i)for (int j(1); j <= m; ++j)if (cen[i][j])list[find(cen[i][j])].push_back({ i, j });
    ll odp(0);
    for (int i(1); i <= q; ++i)
    {
        int min(1e9);
        for (auto j : list[i])for (dir d(U); d < M; d = dir(d + 1))
        {
            add[s(j, d).y][s(j, d).x] = 1;
            if (min > osc(s(j, d)))min = osc(s(j, d));
        }
        if(min != 1e9)odp -= min;
    }
    for (int i(1); i <= n; ++i)for (int j(1); j <= m; ++j)odp += ll(add[i][j])* wart[i][j];
    std::cout << odp << '\n';
    return 0;
}

Compilation message (stderr)

covering.cpp: In function 'int tet(pun)':
covering.cpp:77:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     if (c.x < 0 || c.x >= add.size() || c.y < 0 || c.y >= add[0].size())return 1;
      |                    ~~~~^~~~~~~~~~~~~
covering.cpp:77:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     if (c.x < 0 || c.x >= add.size() || c.y < 0 || c.y >= add[0].size())return 1;
      |                                                    ~~~~^~~~~~~~~~~~~~~~
covering.cpp: In function 'bool upd(pun)':
covering.cpp:100:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     if (c.x < 0 || c.x >= add.size() || c.y < 0 || c.y >= add[0].size())return 1;
      |                    ~~~~^~~~~~~~~~~~~
covering.cpp:100:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     if (c.x < 0 || c.x >= add.size() || c.y < 0 || c.y >= add[0].size())return 1;
      |                                                    ~~~~^~~~~~~~~~~~~~~~
covering.cpp: In function 'int main()':
covering.cpp:148:31: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  148 |         add[a][b] = cen[a][b] = i;

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 30