Submission #598148

#	Time	Username	Problem	Language	Result	Execution time	Memory
598148		Ozy	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	523 ms	15648 KiB

street_lamps

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)

#define MAX 300000

struct x {
    lli padre;
    lli val;
    lli prof;
};

string st;
lli q,n,a,b,res,pa,pb,dif;
x uf[MAX+3];
pair<lli,lli> aa,bb;

void une(lli a, lli b,lli peso) {

    if (uf[b].prof > uf[a].prof) swap(a,b);

    uf[b].padre = a;
    uf[b].val = peso;
    if (uf[b].prof == uf[a].prof) uf[a].prof++;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    cin >> st;
    rep(i,1,n+1) uf[i] = {i,0,1};

    rep(i,0,n-1) if (st[i] == '1') {
        a = i+1;
        while (a != uf[a].padre) a = uf[a].padre;
        une(a,i+2,0);
    }

    rep(t,1,q) {
        cin >> st >> a;

        if (st[0] == 't') {
            b = a+1;

            while (a != uf[a].padre) a = uf[a].padre;
            while (b != uf[b].padre) b = uf[b].padre;
            une(a,b,t);
        }
        else {
            cin >> b;

            aa = {a,0};
            while (uf[ aa.first ].padre != aa.first) {aa.first = uf[aa.first].padre; aa.second++;}
            bb = {b,0};
            while (uf[ bb.first ].padre != bb.first) {bb.first = uf[bb.first].padre; bb.second++;}

            if (aa.first != bb.first) {cout << 0 << endl; continue;}

            pa = aa.second;
            pb = bb.second;

            if (pb > pa) {
                swap(a,b);
                swap(pa,pb);
            }

            res = 0;
            dif = pa-pb;
            rep(i,1,dif) {
                res = max(res,uf[a].val);
                a = uf[a].padre;
            }

            while (a != b) {
                res = max(res,uf[a].val);
                res = max(res,uf[b].val);
                a = uf[a].padre;
                b = uf[b].padre;
            }

            res = t - res;
            cout << res << endl;
        }
    }
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20