Submission #1182602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182602		jerzyk	Road Service 2 (JOI24_ho_t5)	C++20	43 / 100	3098 ms	70032 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<20;
int tab[N], cst[N], lst1[N], whend[N];

int jp[N][21][2];

int fau[N], l[N], r[N], h[N];

int czy[N]; vector<int> aktz;

int pos[N];
pair<int, int> ran[N];

int akt[N];

int k = 0;
vector<pair<int, int>> dp[N];

int Find(int a)
{
    if(fau[a] == a) return a;
    return (fau[a] = Find(fau[a]));
}

void Union(int a, int b)
{
    fau[Find(b)] = Find(a);
}

void LiczJP(int n)
{
    for(int i = n; i >= 1; --i)
    {
        int a = whend[lst1[i]];
        jp[i][0][0] = max(i, whend[lst1[i]]);
        jp[i][0][1] = max(whend[lst1[a]], whend[i]);
    }
}

void DoR(int n, int m)
{
    vector<pair<pair<int, int>, int>> aktr;
    for(int i = 1; i <= n * m; ++i)
    {
        if(fau[i] != i) continue;
        aktr.pb(make_pair(make_pair(r[i], -l[i]), i));
        whend[l[i]] = max(whend[l[i]], r[i]);
    }
    for(int i = 1; i <= n; ++i) whend[i] = max(whend[i], whend[i - 1]);
    sort(aktr.begin(), aktr.end());
    k = (int)aktr.size();
    for(int i = 1; i <= k; ++i)
    {
        ran[i] = aktr[i - 1].st;
        swap(ran[i].st, ran[i].nd);
        ran[i].st *= -1;
        pos[aktr[i - 1].nd] = i;
    }
}

int BS(int q, int x)
{
    int p = 1, k = q, s;
    while(p < k)
    {
        s = (p + k + 1) / 2;
        if(ran[akt[s]].st <= x) p = s;
        else k = s - 1;
    }
    return p + 1;
}

void Do(int i, pair<int, int> cur, int q)
{
    int v = akt[i], l1 = cur.nd, l2 = cur.nd, dod = 1;
    if(lst1[l2] >= ran[akt[1]].st)
        l2 = max(l2, whend[lst1[l2]]);
    while(l1 < ran[v].st)
    {
        ++dod;
        int nl1 = max(l2, whend[lst1[l1]]), nl2 = max(whend[l1], whend[lst1[l2]]);

        if(l1 >= nl1 && l2 >= nl2) return;

        l1 = nl1; l2 = nl2;
    }
    //cout << "H: " << cur.st << " " << cur.nd << "\n";
    //cout << l1 << " " << l2 << " " << dod << " " << l1 << " " << BS(q, l1) << "\n";
    l1 = min(l1, ran[v].nd); l2 = min(l2, ran[v].nd);
    if(lst1[l1] >= ran[v].st)
        dp[BS(q, lst1[l1])].pb(make_pair(cur.st + dod - 1 + 1, whend[lst1[l1]]));
    dp[BS(q, l1)].pb(make_pair(cur.st + dod - 1 + 2, whend[l1]));

    if(lst1[l2] >= ran[v].st)
        dp[BS(q, lst1[l2])].pb(make_pair(cur.st + dod + 1, whend[lst1[l2]]));
    dp[BS(q, l2)].pb(make_pair(cur.st + dod + 2, whend[l2]));
}

void DoQ(int n, int m)
{
    int a, b, il, q = 0;
    cin >> il;
    for(int i = 1; i <= il; ++i)
    {
        cin >> a >> b;
        int x = (a - 1) * m + b;
        x = Find(x);
        if(czy[x]) continue;
        czy[x] = 1; aktz.pb(x);
        ++q;
        akt[q] = pos[x];
    }
    for(int i = 0; i < (int)aktz.size(); ++i) czy[aktz[i]] = 0;
    aktz.clear();
    if(q == 1)
    {
        cout << 0 << "\n";
        return;
    }
    sort(akt + 1, akt + 1 + q);
    int xd = 0;
    for(int i = 1; i <= q; ++i)
        if(ran[akt[i]].st > xd)
        {
            xd = ran[akt[i]].st;
            aktz.pb(akt[i]);
        }

    for(int i = 0; i < (int)aktz.size(); ++i)
        akt[i + 1] = aktz[i];
    q = (int)aktz.size();
    aktz.clear();
    //reverse(akt + 1, akt + 1 + q);
    
    //cout << "\nQ:\n";
    //for(int i = 1; i <= q; ++i)
        //cout << ran[akt[i]].st << " " << ran[akt[i]].nd << "\n";
    dp[1].pb(make_pair(0, ran[akt[1]].nd));
    for(int i = 1; i <= q; ++i)
    {
        sort(dp[i].begin(), dp[i].end());
        if((int)dp[i].size() == 0) continue;
        pair<int, int> a1 = dp[i][0], a2;
        int j = 0;
        while(j < (int)dp[i].size() - 1 && dp[i][j + 1].st == a1.st)
            ++j;
        a1 = dp[i][j];
        while(j < (int)dp[i].size() - 1 && dp[i][j + 1].st == a1.st + 1)
            ++j;
        a2 = dp[i][j];
        //cout << "C1: " << a1.st << " " << a1.nd << " | C2: " << a2.st << " " << a2.nd << "\n";
        Do(i, a1, q);
        Do(i, a2, q);
        dp[i].clear();
    }
    sort(dp[q + 1].begin(), dp[q + 1].end());
    if((int)dp[q + 1].size() == 0)
        cout << -1 << "\n";
    else
        cout << dp[q + 1][0].st << "\n";
    dp[q + 1].clear();
}

void Solve()
{
    int n, m, q;
    char z;
    cin >> n >> m >> q;
    for(int i = 1; i <= n * m; ++i)
    {fau[i] = i; l[i] = n * m + 1; r[i] = 0;}
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j < m; ++j)
        {
            cin >> z;
            if(z == '1')
                Union((i - 1) * m + j, (i - 1) * m + j + 1);
        }
    for(int i = 1; i < n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            cin >> z;
            if(z == '1')
                Union((i - 1) * m + j, (i - 1) * m + j + m);
        }
    for(int i = 1; i <= n; ++i)
    {
        whend[i] = i;
        cin >> cst[i];
        lst1[i] = lst1[i - 1];
        if(cst[i] == 1) lst1[i] = i;
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            int x = (i - 1) * m + j;
            x = Find(x);
            l[x] = min(l[x], i); r[x] = max(r[x], i);
            h[x] = max(h[x], j);
        }

    DoR(n, m);

    for(int i = 1; i <= q; ++i)
        DoQ(n, m);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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