Submission #1214721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214721		badge881	T-Covering (eJOI19_covering)	C++20	100 / 100	249 ms	58128 KiB

covering

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define mp make_pair
#define pb push_back

using ll = long long;
using ld = long double;

const int mxn = 1e6 + 5;
const int SQRT = 500;
const int LOG = 20;
const int inf = 1e18;
const int mod = 1e9 + 7;
const ld eps = 1e-9;

int A[mxn];

vector<int> g[mxn];

int dir[4][2] = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1}};

int n, m;

bool in(int x, int y)
{
    return x >= 0 && y >= 0 && x < n && y < m;
}

bool cen[mxn];
bool vis[mxn];

int ccnt = 0;
vector<int> cmp;

void dfs(int x)
{
    vis[x] = true;
    if (!cen[x])
        cmp.push_back(A[x]);
    else
        ccnt++;

    for (auto v : g[x])
    {
        if (vis[v])
            continue;
        dfs(v);
    }
}

inline int hesh(int a, int b)
{
    return a * m + b;
}

signed main()
{
    scanf("%d%d\n", &n, &m);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%lld", &A[hesh(i, j)]);
        
    
    int k;
    scanf("%lld", &k);
    int ans = 0;

    for (int i = 0; i < k; i++)
    {
        int x, y;
        scanf("%lld %lld", &x, &y);
        int u = hesh(x, y);

        cen[u] = true;
        ans += A[u];
        for (int j = 0; j < 4; j++)
        {
            int nx = x + dir[j][0];
            int ny = y + dir[j][1];

            if (!in(nx, ny))
                continue;
            int v = hesh(nx, ny);

            g[u].push_back(v);
            g[v].push_back(u);
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int u = hesh(i, j);

            if (!vis[u] && cen[u])
            {
                ccnt = 0;
                cmp.clear();

                dfs(u);

                if (cmp.size() < 3 * ccnt)
                {
                    cout << "No" << endl;
                    return 0;
                }

                sort(cmp.begin(), cmp.end());

                for (int k = 1; k <= 3 * ccnt; k++)

                    ans += cmp[cmp.size() - k];
            }
        }
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

covering.cpp: In function 'int main()':
covering.cpp:64:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   64 |     scanf("%d%d\n", &n, &m);
      |            ~^       ~~
      |             |       |
      |             int*    long long int*
      |            %lld
covering.cpp:64:15: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   64 |     scanf("%d%d\n", &n, &m);
      |              ~^         ~~
      |               |         |
      |               int*      long long int*
      |              %lld
covering.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d%d\n", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
covering.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |             scanf("%lld", &A[hesh(i, j)]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
covering.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     scanf("%lld", &k);
      |     ~~~~~^~~~~~~~~~~~
covering.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%lld %lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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