oj.uz

Submission #42408

# Submission time Handle Problem Language Result Execution time Memory
42408 2018-02-26T17:38:06 Z dqhungdl 물병 (JOI14_bottle) C++14
100 / 100
 1940 ms 285504 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5880 KB Output is correct
2 Correct 13 ms 7424 KB Output is correct
3 Correct 14 ms 7796 KB Output is correct
4 Correct 376 ms 10020 KB Output is correct
5 Correct 360 ms 11372 KB Output is correct
6 Correct 356 ms 12784 KB Output is correct
7 Correct 346 ms 14048 KB Output is correct
8 Correct 361 ms 15956 KB Output is correct
9 Correct 359 ms 17224 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 36160 KB Output is correct
2 Correct 44 ms 36160 KB Output is correct
3 Correct 324 ms 55588 KB Output is correct
4 Correct 465 ms 61912 KB Output is correct
5 Correct 548 ms 69020 KB Output is correct
6 Correct 335 ms 69020 KB Output is correct
7 Correct 494 ms 74000 KB Output is correct
8 Correct 567 ms 81004 KB Output is correct
9 Correct 675 ms 91440 KB Output is correct
10 Correct 350 ms 91440 KB Output is correct
11 Correct 396 ms 91440 KB Output is correct
12 Correct 204 ms 91440 KB Output is correct
13 Correct 248 ms 91844 KB Output is correct
14 Correct 190 ms 97900 KB Output is correct
15 Correct 226 ms 99712 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 99712 KB Output is correct
2 Correct 36 ms 99712 KB Output is correct
3 Correct 284 ms 106320 KB Output is correct
4 Correct 451 ms 114220 KB Output is correct
5 Correct 530 ms 121560 KB Output is correct
6 Correct 654 ms 132032 KB Output is correct
7 Correct 344 ms 132032 KB Output is correct
8 Correct 501 ms 132032 KB Output is correct
9 Correct 250 ms 132032 KB Output is correct
10 Correct 271 ms 132680 KB Output is correct
11 Correct 248 ms 136020 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 148032 KB Output is correct
2 Correct 1366 ms 204704 KB Output is correct
3 Correct 360 ms 204704 KB Output is correct
4 Correct 1735 ms 224900 KB Output is correct
5 Correct 1940 ms 243372 KB Output is correct
6 Correct 994 ms 243372 KB Output is correct
7 Correct 394 ms 243372 KB Output is correct
8 Correct 167 ms 243372 KB Output is correct
9 Correct 1741 ms 272240 KB Output is correct
10 Correct 1396 ms 272240 KB Output is correct
11 Correct 1758 ms 285504 KB Output is correct
12 Correct 1617 ms 285504 KB Output is correct