Submission #42408

#	Time	Username	Problem	Language	Result	Execution time	Memory
42408		dqhungdl	물병 (JOI14_bottle)	C++14	100 / 100	1940 ms	285504 KiB

bottle

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

typedef pair<int,int> ii;
typedef pair<int,ii> iii;
int X[]={0,0,-1,1};
int Y[]={-1,1,0,0};
int m,n,k,T,R[200005],h[200005],Com[200005],P[200005][20],maxd[200005][20],d[2005][2005],Pre[2005][2005];
ii Imp[200005];
char a[2005][2005];
vector<ii> g[200005];
vector<iii> Edge;
queue<ii> Q;

int Find(int u)
{
    if(u==R[u])
        return u;
    return R[u]=Find(R[u]);
}

void Union(int u,int v)
{
    if(u>v)
        R[u]=v;
    else
        R[v]=u;
}

void InitTree()
{
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            d[i][j]=-1;
    for(int i=1;i<=k;i++)
    {
        Pre[Imp[i].first][Imp[i].second]=i;
        d[Imp[i].first][Imp[i].second]=0;
        Q.push(Imp[i]);
    }
    while(Q.size()>0)
    {
        int u=Q.front().first;
        int v=Q.front().second;
        Q.pop();
        for(int i=0;i<=3;i++)
        {
            int uu=u+X[i];
            int vv=v+Y[i];
            if(uu>0&&uu<=m&&vv>0&&vv<=n&&a[uu][vv]!='#')
            {
                if(d[uu][vv]==-1)
                {
                    Q.push(ii(uu,vv));
                    d[uu][vv]=d[u][v]+1;
                    Pre[uu][vv]=Pre[u][v];
                }
                else
                if(Pre[uu][vv]!=Pre[u][v])
                    Edge.push_back(iii(d[u][v]+d[uu][vv],ii(Pre[u][v],Pre[uu][vv])));
            }
        }
    }
    for(int i=1;i<=k;i++)
        R[i]=i;
    sort(Edge.begin(),Edge.end());
    for(int i=0;i<Edge.size();i++)
    {
        int u=Find(Edge[i].second.first);
        int v=Find(Edge[i].second.second);
        if(u!=v)
        {
            g[Edge[i].second.first].push_back(ii(Edge[i].second.second,Edge[i].first));
            g[Edge[i].second.second].push_back(ii(Edge[i].second.first,Edge[i].first));
            Union(u,v);
        }
    }
}

void DFS(int u,int high,int kk)
{
    Com[u]=kk;
    h[u]=high;
    for(int i=0;i<g[u].size();i++)
        if(h[g[u][i].first]==0)
        {
            P[g[u][i].first][0]=u;
            maxd[g[u][i].first][0]=g[u][i].second;
            DFS(g[u][i].first,high+1,kk);
        }
}

int LCA(int u,int v)
{
    int rs=0;
    for(int t=18;t>=0;t--)
        if(h[P[u][t]]>=h[v])
        {
            rs=max(rs,maxd[u][t]);
            u=P[u][t];
        }
        else
        if(h[P[v][t]]>=h[u])
        {
            rs=max(rs,maxd[v][t]);
            v=P[v][t];
        }
    for(int t=18;t>=0;t--)
        if(P[u][t]!=P[v][t])
        {
            rs=max(rs,maxd[u][t]);
            rs=max(rs,maxd[v][t]);
            u=P[u][t];
            v=P[v][t];
        }
    while(u!=v)
    {
        rs=max(rs,maxd[u][0]);
        rs=max(rs,maxd[v][0]);
        u=P[u][0];
        v=P[v][0];
    }
    return rs;
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    //freopen("TEST.OUT","w",stdout);
    cin>>m>>n>>k>>T;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    for(int i=1;i<=k;i++)
        cin>>Imp[i].first>>Imp[i].second;
    InitTree();
    int Count=0;
    for(int i=1;i<=k;i++)
        if(h[i]==0)
            DFS(i,1,++Count);
    for(int t=1;t<=18;t++)
        for(int i=1;i<=k;i++)
        {
            P[i][t]=P[P[i][t-1]][t-1];
            maxd[i][t]=max(maxd[i][t-1],maxd[P[i][t-1]][t-1]);
        }
    int u,v;
    while(T--)
    {
        cin>>u>>v;
        if(Com[u]!=Com[v])
            cout<<-1<<"\n";
        else
            cout<<LCA(u,v)<<"\n";
    }
}

Compilation message (stderr)

bottle.cpp: In function 'void InitTree()':
bottle.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<Edge.size();i++)
                  ^
bottle.cpp: In function 'void DFS(int, int, int)':
bottle.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[u].size();i++)
                  ^

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