제출 #1136154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136154		Szymon_Pilipczuk	Road Service 2 (JOI24_ho_t5)	C++20	27 / 100	1660 ms	711412 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;
int csp = 0;
vector<vector<int>> jm[21];
vector<int> mx;
vector<int> mx2;
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(h);
        for(int i = 0;i<h;i++)
        {
            jm[o][i].resize(3);
        }
    }
    mx.resize(h);
    mx2.resize(h);
    for(int i = 0;i<csp;i++)
    {
        for(int j = spp[i].first;j<=spp[i].second;j++)
        {
            if(cs[j] == 1)
            {
                jm[0][j][1] = max(jm[0][j][1],spp[i].second);
            }
            else
            {
                jm[0][j][2] = max(jm[0][j][2],spp[i].second);
            }

        }
    }
    for(int i = 0;i<h;i++)
    {
        jm[0][i][2] = max(jm[0][i][2],jm[0][jm[0][i][1]][1]);
    }
    for(int i = 0;i<h;i++)
    {
        jm[0][i][0] = i;
    }
    for(int o = 1;o<21;o++)
    {
        for(int i = 0;i<h;i++)
        {
            jm[o][i][0] = max(jm[o-1][jm[o-1][i][0]][1],jm[o-1][jm[o-1][i][1]][0]);
            jm[o][i][1] = max(jm[o-1][jm[o-1][i][2]][0],jm[o-1][jm[o-1][i][1]][1]);
            jm[o][i][2] = max(jm[o-1][jm[o-1][i][1]][2],jm[o-1][jm[o-1][i][2]][1]);
        }
    }
    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 = spp[sp[a][b]].second;
        int cu = jm[0][cu0][1];
        int cu2 = jm[0][cu0][2];
        if(cu >= spp[sp[x][y]].first)
        {
            cout<<check(spp[sp[x][y]].first,min(cu,spp[sp[x][y]].second))+1<<"\n";
            continue;
        }
        int ans = 1;
        for(int o = 20;o>=0;o--)
        {
            if(max(jm[o][cu2][0],jm[o][cu][1]) < spp[sp[x][y]].first)
            {
                int cc = jm[o][cu2][0];
                cu0 = max(jm[o][cu0][1],jm[o][cu][0]);
                cu2 = max(jm[o][cu][2],jm[o][cu2][1]);
                cu = max(jm[o][cu][1],cc);
                ans+=(1<<o);
            }
        }
        cu = max(jm[0][cu0][2],jm[0][cu][1]);
        ans++;
        if(cu < spp[sp[x][y]].first)
        {
            cout<<-1<<"\n";
            continue;
        }
        cout<<ans+check(spp[sp[x][y]].first,min(cu,spp[sp[x][y]].second))<<"\n";
    }
}

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