Submission #1136461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136461		Szymon_Pilipczuk	Road Service 2 (JOI24_ho_t5)	C++20	0 / 100	871 ms	1114112 KiB

Main

#include <bits/stdc++.h>
using namespace std;
vector<vector<vector<bool>>> gr;
vector<int> cs;
vector<vector<int>> sp;
vector<pair<int,int>> spp;
vector<vector<int>> jm[21];
vector<pair<int,int>> mx;
int csp = 0;
int h,w,q;
void dfs(int i,int j,int s)
{
    spp[s].first = min(spp[s].first,i);
    spp[s].second = max(spp[s].second,i);
    sp[i][j] = s;
    if(gr[i][j][0] && sp[i-1][j] == -1)
    {
        dfs(i-1,j,s);
    }
    if(gr[i][j][1] && sp[i][j+1] == -1)
    {
        dfs(i,j+1,s);
    }
    if(gr[i][j][2] && sp[i+1][j] == -1)
    {
        dfs(i+1,j,s);
    }
    if(gr[i][j][3] && sp[i][j-1] == -1)
    {
        dfs(i,j-1,s);
    }
}
vector<int> tr;
void add(int p,int v)
{
    p+=h;
    tr[p] = v;
    p/=2;
    while(p > 0)
    {
        tr[p] = min(tr[p*2],tr[p*2+1]);
        p/=2;
    }
}
int check(int l,int r)
{
    l+=h;
    r+=h;
    int ans = min(tr[l],tr[r]);
    while(l/2 != r/2)
    {
        if(l%2 == 0) ans = min(ans,tr[l+1]);
        if(r%2 == 1) ans = min(ans, tr[r-1]);
        l/=2;r/=2;
    }
    return ans;
}
int main()
{
    cin>>h>>w>>q;
    gr.resize(h);
    sp.resize(h);
    for(int i = 0;i<h;i++)
    {
        sp[i].resize(w);
        gr[i].resize(w);
        for(int j =0;j<w;j++)
        {
            sp[i][j] = -1;
            gr[i][j].resize(4);
        }
    }
    for(int i =0;i<h;i++)
    {
        for(int j = 0;j<w-1;j++)
        {
            char c;
            cin>>c;
            if(c == '1')
            {
                gr[i][j][1] = true;
                gr[i][j+1][3] = true;
            }
        }
    }
    for(int i = 0;i<h-1;i++)
    {
        for(int j = 0;j<w;j++)
        {
            char c;
            cin>>c;
            if(c == '1')
            {
                gr[i][j][2] = true;
                gr[i+1][j][0] =true;
            }
        }
    }
    cs.resize(h);
    tr.resize(h*2);
    for(int i  =0;i<h;i++)
    {
        cin>>cs[i];
        add(i,cs[i]);
    }
    for(int i = 0;i<h;i++)
    {
        for(int j = 0;j<w;j++)
        {
            if(sp[i][j] == -1)
            {
                spp.push_back({i,i});
                dfs(i,j,csp);
                csp++;
            }
        }
    }
    for(int o = 0;o<21;o++)
    {
        jm[o].resize(csp);
        for(int i = 0;i<csp;i++)
        {
            jm[o][i].resize(3);
        }
    }
    mx.resize(h);
    for(int i = 0;i<csp;i++)
    {
        for(int j = spp[i].first;j<=spp[i].second;j++)
        {
            if(spp[i].second >= mx[j].first)
            {
                mx[j].first = spp[i].second;
                mx[j].second = i;
            }
        }
    }
    for(int i = 0;i<csp;i++)
    {
        jm[0][i][0] = i;
        jm[0][i][1] = i;
        jm[0][i][2] = i;
        for(int j = spp[i].first;j<=spp[i].second;j++)
        {
            if(cs[j] == 1)
            {
                if(spp[jm[0][i][1]].second < mx[j].first)
                {
                    jm[0][i][1] = mx[j].second;
                }
            }
            if(cs[j] == 2)
            {
                if(spp[jm[0][i][2]].second < mx[j].first)
                {
                    jm[0][i][2] =mx[j].second;
                }
            }
        }
    }
    //cout<<jm[0][0][1]<<" "<<spp[jm[0][0][1]].first<<" "<<spp[jm[0][0][1]].second;
    for(int i = 0;i<csp;i++)
    {
        if(spp[jm[0][i][2]].second < spp[jm[0][jm[0][i][1]][1]].second)
        {
            jm[0][i][2] = jm[0][jm[0][i][1]][1];
        }
    }
    for(int o = 1;o<21;o++)
    {
        for(int i = 0;i<csp;i++)
        {
            if(spp[jm[o-1][jm[o-1][i][0]][1]].second < spp[jm[o-1][jm[o-1][i][1]][0]].second)
            {
                jm[o][i][0] = jm[o-1][jm[o-1][i][1]][0];
            }
            else
            {
                jm[o][i][0] = jm[o-1][jm[o-1][i][0]][1];
            }
            if(spp[jm[o-1][jm[o-1][i][2]][0]].second < spp[jm[o-1][jm[o-1][i][1]][1]].second)
            {
                jm[o][i][1] = jm[o-1][jm[o-1][i][1]][1];
            }
            else
            {
                jm[o][i][1] = jm[o-1][jm[o-1][i][2]][0];
            }
            if(spp[jm[o-1][jm[o-1][i][1]][2]].second < spp[jm[o-1][jm[o-1][i][2]][1]].second)
            {
                jm[o][i][2] = jm[o-1][jm[o-1][i][2]][1];
            }
            else
            {
                jm[o][i][2] = jm[o-1][jm[o-1][i][1]][2];
            }
        }
    }
    for(int i = 0;i<q;i++)
    {
        int t;
        cin>>t;
        int a,b;
        cin>>a>>b;
        a--;b--;
        int x,y;
        cin>>x>>y;
        x--;y--;
        if(spp[sp[a][b]].first > spp[sp[x][y]].first)
        {
            swap(a,x);
            swap(b,y);
        }
        if(sp[a][b] == sp[x][y])
        {
            cout<<0<<"\n";
            continue;
        }
        if(spp[sp[a][b]].second >= spp[sp[x][y]].first)
        {
            cout<<check(spp[sp[x][y]].first,min(spp[sp[a][b]].second,spp[sp[x][y]].second))<<"\n";
            continue;
        }
        int cu0 =sp[a][b];
        int cu = jm[0][cu0][1];
        int cu2 = jm[0][cu0][2];
        if(spp[cu].second >= spp[sp[x][y]].first)
        {
            cout<<check(spp[sp[x][y]].first,min(spp[cu].second,spp[sp[x][y]].second))+1<<"\n";
            continue;
        }
        /*if(i == 0)
        {
            cout<<" A ";
        }*/
        int ans = 1;
        for(int o = 20;o>=0;o--)
        {
            //cout<<cu<<" "<<spp[cu].first<<" "<<spp[cu].second<<"\n";
            //cout<<spp[jm[0][cu2][0]].second<<" "<<spp[jm[0][cu][1]].second<<" "<<spp[sp[x][y]].first<<"\n\n";
            if(max(spp[jm[o][cu2][0]].second,spp[jm[o][cu][1]].second) < spp[sp[x][y]].first)
            {
                int cc = jm[o][cu2][0];
                if(spp[jm[o][cu0][1]].second < spp[jm[o][cu][0]].second)
                {
                    cu0 = jm[o][cu][0];
                }
                else
                {
                    cu0 = jm[o][cu0][1];
                }
                if(spp[jm[o][cu][2]].second < spp[jm[o][cu2][1]].second)
                {
                    cu2 = jm[o][cu2][1];
                }
                else
                {
                    cu2 = jm[o][cu][2];
                }
                if(spp[cc].second < spp[jm[o][cu][1]].second)
                {
                    cu = jm[o][cu][1];
                }
                else
                {
                    cu = cc;
                }
                ans+=(1<<o);
            }
        }
        if(spp[jm[0][cu][1]].second < spp[jm[0][cu0][2]].second)
        {
            cu = jm[0][cu0][2];

        }
        else
        {
            cu = jm[0][cu][1];
        }
        ans++;
        if(spp[cu].second < spp[sp[x][y]].first)
        {
            cout<<-1<<"\n";
            continue;
        }
        cout<<ans+check(spp[sp[x][y]].first,min(spp[cu].second,spp[sp[x][y]].second))<<"\n";
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 6
• Subtask 3: 0 / 15
• Subtask 4: 0 / 11
• Subtask 5: 0 / 6
• Subtask 6: 0 / 12
• Subtask 7: 0 / 26
• Subtask 8: 0 / 14