提出 #57561766

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define f(n, i, x) for (int i = x; i < n; i++)
#define vb push_back
#define ll long long
class DSU
{
public:
    vector<vector<int>> parent;

    DSU(int n)
    {
        parent.resize(n, vector<int>(4));
        for (int i = 0; i < n; ++i)
        {
            parent[i][0] = i;
            parent[i][1] = i;
            parent[i][2] = i;
            parent[i][3] = i;
        }
    }

    int find(int x, int y)
    {

        if (parent[x][y] == x)
            return x;
        return parent[x][y]=find(parent[x][y], y);
    }
};

bool isp(int l1,int r1, int n, int m)
{
    return l1>=0&&l1<n&&r1>=0&&r1<m;
}
void update(DSU &dsu, int l1, int r1, int n, int m)
{
    if (isp(l1,r1+1, n, m))
    {
        dsu.parent[l1 * m + r1][0] = dsu.find(l1 * m + r1 + 1, 0);
        // cout<<dsu.parent[l1*m+r1][0]/m<<' '<<dsu.parent[l1*m+r1][0]%m<<endl;
    }
    if (isp(l1 ,  r1 - 1, n, m))
    {
        dsu.parent[l1 * m + r1][1] = dsu.find(l1 * m + r1 - 1, 1);
        // cout<<dsu.parent[l1*m+r1][1]/m<<' '<<dsu.parent[l1*m+r1][1]%m<<endl;
    }
    if (isp(l1-1,r1, n, m))
    {
        dsu.parent[l1 * m + r1][2] = dsu.find((l1 - 1) * m + r1, 2);
        // cout<<dsu.parent[l1*m+r1][2]/m<<' '<<dsu.parent[l1*m+r1][2]%m<<endl;
    }
    if (isp(l1 + 1 , r1, n, m))
    {
        dsu.parent[l1 * m + r1][3] = dsu.find((l1 + 1) * m + r1, 3);
        // cout<<dsu.parent[l1*m+r1][3]/m<<' '<<dsu.parent[l1*m+r1][3]%m<<endl;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, q;
    cin >> n >> m >> q;
    DSU dsu(n * m + 1);
    vector<int> vis(n * m + 1, 0);
    int ans = 0;
    f(q, i, 0)
    {
        int l1, r1;
        cin >> l1 >> r1;
        l1--, r1--;
        if (!vis[l1 * m + r1])
        {
            vis[l1 * m + r1] = 1;
            ans++;
            // cout << l1 << ' ' << r1 << endl;
            update(dsu, l1, r1, n, m);
            
        }
        else
        {
            int pr = dsu.parent[l1 * m + r1][0];
            if (isp(pr/m,pr%m, n, m) && !vis[pr])
            {
                ans++;
                // cout << pr / m << ' ' << pr % m << endl;
                vis[pr] = 1;
                update(dsu, pr / m, pr % m, n, m);
            }
            pr = dsu.parent[l1 * m + r1][1];

            if (isp(pr/m,pr%m, n, m) && !vis[pr])
            {

                ans++;
                // cout << pr / m << ' ' << pr % m << endl;
                vis[pr] = 1;
                update(dsu, pr / m, pr % m, n, m);
            }
            pr = dsu.parent[l1 * m + r1][2];
            if (isp(pr/m,pr%m, n, m) && !vis[pr])
            {
                ans++;
                // cout << pr / m << ' ' << pr % m << endl;
                vis[pr] = 1;
                update(dsu, pr / m, pr % m, n, m);
            }
            pr = dsu.parent[l1 * m + r1][3];
            if (isp(pr/m,pr%m, n, m) && !vis[pr])
            {
                ans++;
                // cout << pr / m << ' ' << pr % m << endl;
                vis[pr] = 1;
                update(dsu, pr / m, pr % m, n, m);
            }
            update(dsu, l1, r1, n, m);
            
        }
        // cout<<endl;
    }
    cout << n * m - ans << endl;
}

提出情報

ジャッジ結果