Submission #1126905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126905		Zbyszek99	Road Service 2 (JOI24_ho_t5)	C++20	16 / 100	1392 ms	429676 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

vi graph[1000'001];
int comp[1000'001];
int y_index[1000'001];
int real_seg[1000'001];
int cost[1000'001];
vector<pair<pii,int>> seg2;
pii seg[1000'001];
int best_seg[1000'001];
int pref[1000'001];
int m;

struct jump_str
{
    int j0,j1,j2;
    int dist = 0;
};

jump_str jump[1000'000][20];

jump_str merge_jumps(jump_str s1, int P)
{
    if(s1.dist == 0) return jump[s1.j0][P];
    jump_str ans;
    ans.dist = s1.dist + (1 << P);
    ans.j0 = max(jump[s1.j0][P].j1,jump[s1.j1][P].j0);
    ans.j1 = max(jump[s1.j0][P].j2,jump[s1.j1][P].j1);
    ans.j2 = max(jump[s1.j1][P].j2,jump[s1.j2][P].j1); 
    return ans;
}

pii dfs(int v)
{
   // cout << v << " dfs\n";
    comp[v] = m;
    pii s = {y_index[v],y_index[v]};
    forall(it,graph[v])
    {
        if(comp[it] == -1)
        {
            pii s2 = dfs(it);
            s.ff = min(s.ff,s2.ff);
            s.ss = max(s.ss,s2.ss);
        }
    }
    return s;
}

pii find_next(int v, int doc)
{
    if(v == doc) return {v,0};
    jump_str cur_jump = {v,v,v,0};
    for(int bit = 19; bit >= 0; bit--)
    {
        jump_str new_jump = merge_jumps(cur_jump,bit);
        if(seg[new_jump.j1].ss < seg[doc].ff)
        {
            cur_jump = new_jump;
        }
    }
    if(seg[cur_jump.j1].ss < seg[doc].ff)
    {
        cur_jump = merge_jumps(cur_jump,0);
    }
    if(seg[cur_jump.j1].ss < seg[doc].ff)
    {
        return {-1,-1};
    }
    v = cur_jump.j1;
    pii collide = {max(seg[doc].ff,seg[v].ff),min(seg[doc].ff,seg[v].ss)};
    if(pref[collide.ss+1] - pref[collide.ff] != 0) return {v,cur_jump.dist+1};
    return {v,cur_jump.dist+2};
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    ll W,H,q;
    cin >> H >> W >> q;
    rep(i,H)
    {
        rep(j,W)
        {
            int cell = i*W+j;
            y_index[cell] = i;
            comp[cell] = -1;
        }
    }
    rep(i,H)
    {
        rep(j,W-1)
        {
            int cell = i*W+j;
            char z;
            cin >> z;
            if(z == '1') 
            {
                graph[cell].pb(cell+1);
                graph[cell+1].pb(cell);
            }
        }
    }
    rep(i,H-1)
    {
        rep(j,W)
        {
            int cell = i*W+j;
            char z;
            cin >> z;
            if(z == '1') 
            {
                graph[cell].pb(cell+W);
                graph[cell+W].pb(cell);
            }
        }
    }
    rep(i,H) cin >> cost[i];
    rep(i,H)
    {
        pref[i+1] = pref[i];
        if(cost[i] == 1)
        pref[i+1]++;
    }
    rep(i,H*W)
    {
        if(comp[i] == -1)
        {
            pii s = dfs(i);
          //  cout << i << " new\n";
            seg2.pb({{s.ss,s.ff},m});
            m++;
        }
    }
    sort(all(seg2));
    rep(i,m)
    {
        seg[i] = {seg2[i].ff.ss,seg2[i].ff.ff};
        real_seg[seg2[i].ss] = i;
      // cout << seg[i].ff << " " << seg[i].ss << " seg\n";
    }
    multiset<int> multi;
    vector<pii> events;
    rep(i,m)
    {
        events.pb({seg[i].ff,i});
        events.pb({seg[i].ss+1,i+m});
    }
    sort(all(events));
    int cur_event = 0;
    set<int> cost1;
    set<int> cost2;
    rep(i,H)
    {
        while(cur_event != siz(events) && events[cur_event].ff == i)
        {
            if(events[cur_event].ss < m)
            {
                multi.insert(events[cur_event].ss);
            }
            else
            {
                multi.erase(multi.find(events[cur_event].ss-m));
            }
            cur_event++;
        }
        auto it = multi.end();
        if(it != multi.begin())
        {
            it--;
            best_seg[i] = *it ;
        }
        if(cost[i] == 1) cost1.insert(i);
        else cost2.insert(i);
    }
    rep(i,m)
    {
        //cost 0
        jump[i][0].j0 = i;
        jump[i][0].j1 = i;
        jump[i][0].j2 = i;
        jump[i][0].dist = 1;
        //cost 1
        auto it = cost1.upper_bound(seg[i].ss);
        if(it != cost1.begin())
        {
            it--;
            jump[i][0].j1 = best_seg[*it];
        }
        //cost 2
        it = cost2.upper_bound(seg[i].ss);
        if(it != cost2.begin())
        {
            it--;
            jump[i][0].j2 = best_seg[*it];
        }
    }
    rep(i,m)
    {
        jump[i][0].j2 = max(jump[i][0].j2,jump[jump[i][0].j1][0].j1);
    }
    rep2(bit,1,19)
    {
        rep(i,m)
        {
            jump[i][bit] = merge_jumps(jump[i][bit-1],bit-1);
        }
    }
    rep(qq,q)
    {
        int t;
        cin >> t;
        vi points;
        rep(j,t)
        {
            int y,x;
            cin >> y >> x;
            y--;
            x--;
            int cell = y*W + x;
            points.pb(real_seg[comp[cell]]);
        }
        sort(all(points));
       // cout << points[0] << " " << points[1] << " points\n";
        cout << find_next(points[0],points[1]).ss << "\n";
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 6 / 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