Submission #1244624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244624		tvgk	물병 (JOI14_bottle)	C++20	30 / 100	1164 ms	284152 KiB

bottle

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e3 + 7, mxX = 2e5 + 7;

int nRow, nCol, vis[mxN][mxN], ans[mxX], dsu[mxN * mxN], n, q;
ii a[mxX];
string s[mxN];
map<int, bool> m[mxN * mxN];
int d1[4] = {0, 0, -1, 1};
int d2[4] = {-1, 1, 0, 0};

bool Check(int u, int v)
{
    return (u < 0) || (v <= u);
}

int Encode(int u, int v)
{
    return u * nCol + v;
}

int Find(int j)
{
    if (dsu[j] == j)
        return j;
    else
        return dsu[j] = Find(dsu[j]);
}

void Union(int u, int v, int dif)
{
    u = Find(u);
    v = Find(v);

    if (u == v)
        return;

    if (m[u].size() > m[v].size())
        swap(u, v);

    dsu[u] = v;
    for (ii i : m[u])
    {
        if (m[v][i.fi])
        {
            ans[i.fi] = dif;
            m[v].erase(i.fi);
        }
        else
            m[v][i.fi] = 1;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> nRow >> nCol >> n >> q;
    for (int i = 0; i < nRow; i++)
    {
        cin >> s[i];
        for (int j = 0; j < nCol; j++)
        {
            int tmp = Encode(i, j);
            dsu[tmp] = tmp;
            vis[i][j] = -1;
        }
    }

    queue<ii> qq;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].fi >> a[i].se;
        a[i].fi--;
        a[i].se--;
        vis[a[i].fi][a[i].se] = 0;
        qq.push(a[i]);
    }

    for (int i = 1; i <= q; i++)
    {
        int u, v;
        cin >> u >> v;

        m[Encode(a[u].fi, a[u].se)][i] = 1;
        m[Encode(a[v].fi, a[v].se)][i] = 1;
        ans[i] = -1;
    }

    while (qq.size())
    {
        ii j = qq.front();
        qq.pop();

        for (int i = 0; i < 4; i++)
        {
            int u = j.fi + d1[i];
            int v = j.se + d2[i];

            if (Check(u, nRow) || Check(v, nCol) || s[u][v] == '#')
                continue;

            Union(Encode(j.fi, j.se), Encode(u, v), vis[j.fi][j.se] + vis[u][v]);
            if (vis[u][v] == -1)
            {
                vis[u][v] = vis[j.fi][j.se] + 1;
                qq.push({u, v});
            }
        }
    }

    for (int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 30 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30