제출 #1197933

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197933		12345678	물병 (JOI14_bottle)	C++20	0 / 100	792 ms	135300 KiB

bottle

#include <bits/stdc++.h>

using namespace std;

const int hx=2e3+5, nx=2e5+5, inf=1e9, kx=19;

int n, m, p, qrs, u, v, x[nx], y[nx], mn[hx][hx], nd[hx][hx], dx[4]={1, 0, 0, -1}, dy[4]={0, 1, -1, 0}, l[2*nx], r[2*nx], t, pa[2*nx][kx], lvl[2*nx], vl[2*nx], dsu[2*nx];
char mp[hx][hx];
vector<tuple<int, int, int>> edg;
queue<pair<int, int>> q;

int find(int x)
{
    if (dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}

void dfs(int u, int p)
{
    lvl[u]=lvl[p]+1;
    pa[u][0]=p;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    if (l[u]) dfs(l[u], u);
    if (r[u]) dfs(r[u], u);
}

int lca(int u, int v)
{
    if (lvl[u]>lvl[v]) swap(u, v);
    for (int i=kx-1; i>=0; i--) if (lvl[pa[v][i]]>=lvl[u]) v=pa[v][i];
    if (u==v) return u;
    for (int i=kx-1; i>=0; i--) if (pa[u][i]!=pa[v][i]) u=pa[u][i], v=pa[v][i];
    return pa[u][0];
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>p>>qrs;
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>>mp[i][j], mn[i][j]=inf;
    for (int i=1; i<=p; i++) cin>>x[i]>>y[i], nd[x[i]][y[i]]=i, mn[x[i]][y[i]]=0, q.push({x[i], y[i]});
    while (!q.empty())
    {
        auto [cx, cy]=q.front();
        q.pop();
        for (int dir=0; dir<4; dir++)
        {
            int newx=cx+dx[dir], newy=cy+dy[dir];
            if (mp[newx][newy]=='.'&&!nd[newx][newy])
            {
                mn[newx][newy]=mn[cx][cy]+1;
                nd[newx][newy]=nd[cx][cy];
                q.push({newx, newy});
            }
        }
    }
    for (int i=1; i<=n; i++) for (int j=1; j<m; j++) if (mp[i][j]=='.'&&mp[i][j+1]=='.'&&nd[i][j]) edg.push_back({mn[i][j]+mn[i][j+1], nd[i][j], nd[i][j+1]});
    for (int i=1; i<n; i++) for (int j=1; j<=m; j++) if (mp[i][j]=='.'&&mp[i+1][j]=='.'&&nd[i][j]) edg.push_back({mn[i][j]+mn[i+1][j], nd[i][j], nd[i+1][j]});
    for (int i=1; i<p; i++) edg.push_back({inf, i, i+1});
    sort(edg.begin(), edg.end());
    for (int i=1; i<=2*p; i++) dsu[i]=i;
    t=p;
    for (auto [w, u, v]:edg)
    {
        if (find(u)!=find(v))
        {
            t++;
            l[t]=find(u), r[t]=find(v), vl[t]=w;
            dsu[find(u)]=dsu[find(v)]=t;
        }
    }
    dfs(t, t);
    while (qrs--) cin>>u>>v, cout<<vl[lca(u, v)]<<'\n';
}

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