Submission #1182092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182092		jerzyk	Road Service 2 (JOI24_ho_t5)	C++20	0 / 100	41 ms	8516 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<<18;
int tab[N], cst[N], lst1[N], lst2[N], whend[N];

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;
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 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);
        pos[aktr[i - 1].nd] = i;
    }
}

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();
    sort(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";
    int s1 = ran[akt[1]].nd, s2 = ran[akt[1]].nd, ct1 = 0, ct2 = 0, ans = 1, lend = N;

    if(q == 1)
    {
        cout << 0 << "\n";
        return;
    }
    if(lst1[s1] < ran[akt[1]].st)
    {
        ans = 3;
        ct1 = ran[akt[1]].nd; s1 = whend[s1];
        ct2 = ct1; s2 = s1;
    }

    for(int i = 2; i <= q; ++i)
    {
        lend = min(lend, ran[akt[i - 1]].st);

        int nct1 = 0, nct2 = 0;
        int v = akt[i];
        while(s2 < ran[v].st)
        {
            ++ans;
            nct1 = ct2; nct1 = max(nct1, lst1[s1]);
            nct2 = lst1[s2]; nct2 = max(nct2, lst2[s1]);
            nct2 = max(nct2, nct1);
            ct1 = nct1; ct2 = nct2;
            if(s1 >= whend[ct1] && s2 >= whend[ct2])
            {
                cout << -1 << "\n";
                return;
            }
            s1 = max(s1, whend[ct1]); s2 = max(s2, whend[ct2]);
        }

        //cout << "C1: " << ct1 << " " << s1 << " C2: " << ct2 << " " << s2 << " ans: " << ans  << "\n";

        if(s2 >= ran[v].nd)
        {
            if(s1 >= ran[v].nd)
            {s2 = s1; ct2 = ct1;}
            if(s1 < ran[v].st)
                {++ans; s1 = s2; ct1 = ct2;}

            if(ct2 >= ran[v].st)
            {
                if(ct1 >= ran[v].st) continue;
                ++ans;
                s1 = s2; ct1 = ct2;
                continue;
            }

            ++ans;
            nct2 = lst1[ran[v].nd];
            if(s1 >= ran[akt[i]].nd) nct2 = max(nct2, lst2[ran[v].nd]);
            else nct2 = max(nct2, lst2[s1]);

            ct2 = nct2; s2 = whend[ct2];

            if(s1 >= ran[akt[i]].nd) nct1 = lst1[ran[v].nd];
            else nct1 = lst1[s1];
            if(nct1 < max(ran[v].st, lend))
            {
                ++ans;
                nct1 = ct2;
                s1 = s2; ct1 = ct2;
            }
            ct1 = nct1; s1 = whend[ct1];
            continue;
        }

        //cout << "1: " << ct1 << " " << s1 << " 2: " << ct2 << " " << s2 << "\n";

        if(s1 >= ran[v].st)
        {s2 = s1; ct2 = ct1; --ans;}
        ct1 = ct2; s1 = s2; ++ans;


        if(lst1[s2] >= max(lend, ran[akt[i]].st))
        {++ans; ct2 = lst1[s2];}
        else
        {ans += 2; ct2 = lst2[s2];}

        s2 = whend[ct2];
        ct1 = ct2; s1 = s2;
    }
    cout << ans - 1 << "\n";
}

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)
    {
        cin >> cst[i];
        lst1[i] = lst1[i - 1]; lst2[i] = lst2[i - 1];
        if(cst[i] == 1) lst1[i] = i;
        else lst2[i] = i;

        lst2[i] = max(lst2[i], lst1[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);
    //cerr << "XD\n";
    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: 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