My thought process on this problem went like "ew this is disgusting implementation" => "oh actually it's not so bad" => "oh no it's actually disgusting implementation"

But I actually enjoyed this one more than most heavy casework/implementation problems because, while you have to be very careful about the dp transitions and especially their order, it's not too hard to prove once you have it written out.

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"BRAK\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 1e6+5;

vector<int> pth; // path from s to t!

int dp1[maxn], dp2[maxn]; // maximum number of free steps after {1: stomping here, 2: being here but not stomping}
vector<pii> run1[maxn], run2[maxn]; // for restoring answer
bool onpth[maxn];

vector<pii> g[maxn]; // {to, edge id}

bool findpth(int v, int T, int p) {
    if (v == T) {
        pth.pb(T); return 1;
    }
    for (pii u : g[v]) {
        if (u.f != p && findpth(u.f,T,v)) {
            pth.pb(v); onpth[u.s] = 1; return 1;
        }
    }
    return 0;
}

#define piii pair<pii,int>

void dfs(int v, int par) {
    dp2[v] = 3; // i'm so free i haven't even stomped yet
    dp1[v] = 2; // yarrr i'm freshly stomped mmm
    run1[v].pb({v, -1});
    vector<piii > us;
    for (pii p : g[v]) {
        int u = p.f;
        if (!onpth[p.s] && p.f != par) {
            // tree edge!
            dfs(u,v);
            us.pb({{dp1[u],dp2[u]}, u});
        }
    }

    sort(ALL(us), [&](piii a, piii b) {
        if (a.f.f == 2 || b.f.f == 2) return a.f.f > b.f.f; // i want to work with walking the leaf nodes first
        if (a.f.f != b.f.f) return a.f.f > b.f.f;
        if (a.f.f == 1) {
            return a.f.s < b.f.s; // waste a bad dp
        }
        return a.f.s < b.f.s; // doesn't matter at this point ig
         } );
    for (auto rr : us) {
        int u = rr.s;

        if (dp2[v] == 3){ // work with node free, this time we haven't stomped yet
            if (dp1[u] == 2) {
                // it's  a leaf or something, anyways we can ignore it after stomping and come back
                run2[v].pb({u,1});
                goto dp2done;
            }else{
                if (dp1[u]==1) { //  i stomp it and come back?
                    run2[v].pb({u,1});
                    run2[v].pb({v,-1});
                    dp2[v] = 2;
                    goto dp2done;
                }else { // all hopeless, i have to stomp myself first
                    run2[v].pb({v,-1});
                    dp2[v] = 2;
                }
            }
        }
        if (dp2[v] == 2) {
            // im forced to have stomped here now
            // this will be equivalent to a later one
            if (dp2[u] == 2) {
                run2[v].pb({u,2});
                dp2[v] = 1;
                goto dp2done;
            }else{
                dp2[v] = 0;
                goto dp2done;
            }
        }
        if (dp2[v] == 1) {
            if (dp1[u] == 2) {
                run2[v].pb({u,1});
                dp2[v] = 1;
                goto dp2done;
            }else{
                dp2[v] = 0;
                goto dp2done;
            }
        }
        dp2done:;
    }
    sort(ALL(us), [&](piii a, piii b) {
        return a.f.f < b.f.f; // you want to waste a bad dp1 early on
         } );
    for (auto rr : us) {
        int u = rr.s;

            if (dp1[v] == 2) {
                if (dp2[u] == 2) {
                    run1[v].pb({u,2});
                    dp1[v] = 1;
                    goto dp1done;
                }else{
                    dp1[v] = 0;
                    goto dp1done;
                }
            }

            if (dp1[v] == 1) {
                if (dp1[u] == 2) {
                    run1[v].pb({u,1});
                    dp1[v] = 1;
                    goto dp1done;
                }else{
                    dp1[v] = 0;
                    goto dp1done;
                }
            }

            dp1done:;

    }
    if (dp2[v] == 3) {
        run2[v].pb({v, -1});
        dp2[v] = 2;
    } // no point in being super free now, 2 is good enough
    assert(dp2[v] >= dp1[v]);
}

vector<int> re;

void prt(int v, int tp) {
    if (tp == -1) {
        re.pb(v); return;
    }
    for (pii p : tp==1?run1[v]:run2[v]) {
        prt(p.f, p.s);
    }
}

signed main(){
    IOS();
    int n; cin>>n;
    REP(i,n-1) {
        int a,b; cin>>a>>b;
        g[a].pb({b,i});
        g[b].pb({a,i});
    }

    findpth(1, n, -1);
    reverse(ALL(pth));

    for (int x : pth) bug(x);

    int can = 1;

    vector<int> tp(SZ(pth));


    REP(i, SZ(pth)) {
        tp[i] = can;
        int v = pth[i];
        dfs(v, -1);
        bug(v, can);
        if (can == 0) GG();
        if (i == SZ(pth)-1 && can == 1 && dp1[v] != 2) GG(); // can't stomp the last one first
        bug(v, dp1[v], dp2[v]);
        if (can == 2) {
            can = dp2[v];
        }else{
            can = dp1[v];
        }
    }
    bug(can);
    if (can == 0 || can == 1) GG();

    REP(i, SZ(pth)) {
        prt(pth[i], tp[i]);
    }

    for (int x : re) cout<<x<<endl;

}

Another heavy implementation problem. Actually, the implementation isn't terrible (if you split the grid into 2N x 2M nodes), but I spent a long time debugging because I didn't realize that most exGCD implementations can't handle negative numbers well...

#include <bits/stdc++.h>
//#undef BALBIT
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define REP(i,n) for (int i = 0; i<n; ++i)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b) % mo;
}

const int maxn = 1e5+5;

int n,m,npts;

pii flip(pii pt, pii dir) {
    if (dir.f == -1 && pt.f) {
        pt.f = 4*m-pt.f;
    }
    if (dir.s == -1 && pt.s) {
        pt.s = 4*n-pt.s;
    }
    return pt;
}

struct point{

};

vector<pair<pii, pii> > from[maxn]; // x=1 or 3, a-value


ll euclid(ll a, ll b, ll &x, ll &y) {
	if (b) { ll d = euclid(b, a % b, y, x);
		return y -= a/b * x, d; }
	return x = 1, y = 0, a;
}


pii get(pii p) {
    int piff = p.f - p.s; bug(piff);
    int x = 0;

    if ((piff-1) % 4 == 0) x = 1;
    else x = 3;

    pii k;
    euclid(-m,n,k.f,k.s);
    if (k.f * -m + k.s * n < 0) {
        k.f *= -1; k.s *= -1;
    }

    int RHS = (piff - x) / 4; assert((piff-x)%4==0);

    k.f *= RHS; k.s *= RHS;

    ll a = p.s + k.s * 4 * n; a %= (4*n*m);
    if (a < 0) a += 4*n*m;

    bug(p.f, p.s, x, a);
    return {x, a};
}

ll smat(vector<pii> var){
    array<set<pair<pii, pii> >, 4> s; // for the two values of x shift

    REP(i,npts) {
        int x,y; tie(x,y) = var[i]; x*=2; y*=2; --x; --y;

        vector<pii> v;
        vector<pii> vf;
        if (x-1!=0){
            // left edge
            v.pb(flip({x-1,y}, {1,-1}));
            v.pb(flip({x-1,y}, {1,+1}));

            vf.pb(flip({x-1,y}, {-1,-1}));
            vf.pb(flip({x-1,y}, {-1,+1}));
        }
        if (x+1!=m*2){
            // right edge
            v.pb(flip({x+1,y}, {-1,-1}));
            v.pb(flip({x+1,y}, {-1,+1}));

            vf.pb(flip({x+1,y}, {1,-1}));
            vf.pb(flip({x+1,y}, {1,+1}));
        }
        if (y+1!=n*2){
            // top edge
            v.pb(flip({x,y+1}, {1,-1}));
            v.pb(flip({x,y+1}, {-1,-1}));

            vf.pb(flip({x,y+1}, {1,1}));
            vf.pb(flip({x,y+1}, {-1,1}));
        }
        if (y-1!=0){
            // bottom edge
            v.pb(flip({x,y-1}, { 1,+1}));
            v.pb(flip({x,y-1}, {-1,+1}));

            vf.pb(flip({x,y-1}, { 1,-1}));
            vf.pb(flip({x,y-1}, {-1,-1}));
        }

        REP(j, SZ(v)) {
            pii p = v[j];
            pii pa = get(p);
            int x = pa.f, a = pa.s;

            pii fop = get(vf[j]);

            from[i].pb({{a, x}, fop});
            s[x].insert({{a, i}, fop});
        }

    }

    pii nowdir = {-1,1};
    pii nowpt = flip({m,0}, nowdir);
    pii A = get(nowpt);

    bug(A.f, A.s);

    pii tmp = get(flip({m-1,1}, nowdir));
    bug(tmp.f, tmp.s);

    ll ret = 0;

    while (SZ(s[1])) {
        auto nxt = s[A.f].lower_bound({{A.s, -1},{-1,-1}});
        if (nxt == s[A.f].end()) nxt = s[A.f].begin();
        ll df = (*nxt).f.f - A.s;
        assert(df != 0);

        if (df < 0) df += 4*n*m; // not sure, maybe 2nm??
        ret += df;

        bug(df, ret);

        A = (*nxt).s;
//        A = get(nowpt);

        int bye = (*nxt).f.s;
        bug(bye);
        for (auto p : from[bye]) {
            int X = p.f.s;
            p.f.s = bye;
            s[X].erase(p);
        }
    }

    return ret;
}

int yo[500][500];

ll dumb(vector<pii> var) {
    int i =0;
    for (pii p : var) {
        int x = p.f, y = p.s; x = x*2-1; y = y*2-1;
        yo[x+1][y]++;
        yo[x][y+1]++;
        yo[x-1][y]++;
        yo[x][y-1]++;
        yo[x][y]=1;
        ++i;
    }
    int x = m, y = 0;
    int dx = -1, dy = 1;
    int bar = 0;
    int re = 0;
    while (bar < npts) {
        x += dx; y += dy; ++re;

        pii tmp = get(flip({x,y}, {dx, dy}));

        bug(x,y,re,tmp.f, tmp.s);
        if (yo[x][y]) {
            // bump!
            REP(ss, 4){
                int tx = (ss-1)%2; //    -1 0 1 0
                int ty = (2-ss)%2; //     0 1 0 -1
                if (yo[tx+x][ty+y]) {
                    int X = tx+x, Y = ty+y;

                    if (tx) dx *= -1;
                    else dy *= -1;

                    for (int sx:{-1,1}) for (int sy:{-1,1}) {
                        --yo[X+sx][Y+sy];
                    }
                    yo[X][Y] = 0;
                    goto yar;
                }
            }

            yar:;

            ++bar;
        }else{
            if (x == 0 || x == 2*m) dx *= -1;
            if (y == 0 || y == 2*n) dy *= -1;
        }
    }
    return re;
}

signed main(){
    IOS();
    cin>>m>>n>>npts; // m is for X, n is for Y

    vector<pii> var;
    REP(i,npts) {
        int x,y; cin>>x>>y; var.pb({x,y});
    }

    cout<< smat(var)<<endl;

//    ll poo = dumb(var);

//    bug(ss, poo);

}

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 5e5+5;

vector<int> g[maxn];
int par[maxn];
int ch[maxn]; // number of white children
bool black[maxn];

void dfs(int v, int p) {
    par[v] = p;
    for (int u : g[v]) {
        if (u != p) {
            dfs(u,v);
            ++ch[v];
        }
    }
}

signed main(){
    IOS();

    int n; cin>>n;
    REP(i,n-1) {
        int a,b; cin>>a>>b;
        g[a].pb(b); g[b].pb(a);
    }
    dfs(1,-1);

    int V = n; int E = n-1;
    int q; cin>>q;
    REP(i,q) {
        int v; cin>>v;
        bool toblack = v>0;
        v = abs(v);
        int p = par[v];
        if (toblack) {
            --V;
            int fr = ch[v] + (p != -1 && !black[p]);
            E -= fr;
            if (p != -1) {
                --ch[p];
            }
        }else{
            ++V;
            int fr = ch[v] + (p != -1 && !black[p]);
            E += fr;
            if (p != -1) {
                ++ch[p];
            }
        }
        black[v] ^= 1;
        cout<<V-E<<endl;
    }

}

I got stuck on Rally for too long and decided to try this one.

Thinking of the solution and implementing it was easy; getting it to pass on szkopul was not.

Not only are time limits different for each subtask, they also vary for each test case, meaning that you'll suffer a lot if you don't implement it in the same way the author did.

Also, I didn't see that there were multiple edges for a while. That was my bad.

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
//#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 1e5+5;

typedef array<ll, 121> Vec;
typedef array<Vec, 121> Mat;

Mat M;
ll cap = (1ll<<61)-1;

int LAY = 65;
Mat Mp[65];


inline ll prod(ll a, ll b) {
    if (!b || !a) return 0;
    if ((a) > (cap) / b + 1) return cap;
    return min(a*b, cap);
}

inline void add(ll &a, ll b) {
    a = min(cap,a+b);
}

int YO, END;

void mul(Mat &c, Mat a, Mat b) {
    REP(i,YO) REP(j,YO) if (i<j) swap(b[i][j], b[j][i]);
    REP(i, YO) REP(j, YO) {
        c[i][j] = 0;
        REP(k,YO) {
            add(c[i][j], prod(a[i][k], b[j][k]));
            if (c[i][j] == cap) break;
        }
    }
}

signed main(){
    IOS();
    int n,m; ll k; cin>>n>>m>>k;

    YO = n*3+1; END = YO-1;

    k += n;

    LAY = __lg(k+1)+2;

    REP(i,n) {
        M[i*3][i*3+1] = 1;
        M[i*3+1][i*3+2] = 1;
    }

    REP(i,m) {
        int a,b,c; cin>>a>>b>>c;
        --a; --b;
        M[a*3+2][b*3+3-c] += 1;
    }

    Vec now; fill(ALL(now), 0);
    REP(i,n) {
        now[i*3+2] = 1;
        M[i*3+2][END] = 1;
    }
    M[END][END] = 1;

    Mp[0] = M;

    ll psig = -1;
    bool yoit = 0;

    REP1(i, LAY-1) {
        bug(i);
        mul(Mp[i], Mp[i-1], Mp[i-1]);
        ll sg = 0;
        REP(p,YO) {
            if (p % 3 == 2)
                add(sg, Mp[i][p][END]);
        }
        if (sg > k ) {
            yoit = 1;
            LAY = i+1; break;
        }
        psig = sg;
    }

    ll re = 0;

    bool big = 0;ll sg= 0;

    for (int mi = LAY-1; mi>=0; --mi) {
        Vec tmp;
        fill(ALL(tmp), 0);
        ll sig = 0;
        REP(i, YO) {
            tmp[i] = 0;
            REP(j,YO) {
                add(tmp[i], prod(now[j], Mp[mi][j][i]));
            }
            if (i == END) {
                add(sig, tmp[i]);
            }
        }
        bug(sig, k);
        if (sig < k) {
            sg = sig;
            re += (1ll<<mi);
            now = tmp;
        }else big = 1;
    }

    if (!big) {
        assert(yoit != 1);
        re = -1;
    }

    cout<<re<<endl;


}

This is a great problem! It feels awesome finding observations and separating this difficult-seeming problem into a few easy-to-handle cases.

One thing that surprised me was that I forgot an entire (fairly important) case that should've been easily caught with a random testcase but was still able to get 84 points, with only 2 subtasks showing WA. I guess this goes to show the importance of multitests, however annoying they are.

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 3e3+5;

vector<pii> dp[maxn]; // {reaches to, cost}
ll smollest[maxn];

signed main(){
    IOS();

    int n,z,d; cin>>n>>z>>d;

    vector<ll> a(n+1);
    vector<ll> sig(n+1);

    ll re = 0;
    REP1(i,n) {
        cin>>a[i];
        if (a[i] < d) {
            re += d-a[i]; a[i] = d;
        }
        if (i - z >= 0 && a[i] - a[i-z] < d) {
            re += a[i-z] + d - a[i];
            a[i] = a[i-z] + d;
        }
        bug(i, a[i]);
        sig[i] = sig[i-1] + a[i];
    }
    a.pb(inf);
    bug(re);

    dp[0].pb({0, 0});

    for (int i = 1; i<=n; ++i) {
        ll cst = 0;
        int ntook = 1;
        int j = i;
        ll base = inf;
        for (; j>0 && ntook <= z && a[i]-a[j] <= d; --j, ++ntook) {
            if (a[i] - a[j] == d) {
                // try transition
                if (dp[j][0].f <= a[j])
                    MN(base, dp[j][0].s + cst);
            }
            cst += a[i] - a[j];
        }

        for (pii p : dp[j]) {
            if (p.f <= a[i] - d) {
                MN(base, p.s + cst);
            }
        }

        for (; j>0 && ntook <= z; --j, ++ntook) {
            cst += a[i] - a[j];
            MN(base, smollest[j-1] + cst);
        }

        bug(i, base);

        int at = i;

        for (int rps = 0; ; ++rps) {
            dp[at].pb({a[i] + rps * d, base});
            ntook = 0;
            for (; a[at] <= a[i] + (rps+1)*d && ntook <= z; ++at, ++ntook) {
                if (ntook) {
                    base += (rps+1)*d + a[i] - a[at];
                }
            }
            if (ntook == 1) break;
            --at;
        }
        smollest[i] = inf;
        for (pii p : dp[i]) {
            MN(smollest[i], p.s);
        }
        sort(ALL(dp[i]), [&](pii x, pii y){return x.f!=y.f?x.f < y.f : x.s < y.s;});
    }

    ll ret = inf;

    {
        ret = smollest[n];
//        for (pii p : dp[n]) MN(ret, p.s);
    }

    cout<<ret + re<<endl;

}


/*
5 5 101
2 100 300 400 500
*/

This was a pretty cute and nice problem! I found it pretty easy but still very nice.

Let $$$f(S)$$$ denote the answer after adding the set of non-MST edges $$$S$$$.

Obviously, because of MST properties, for a non-MST edge $$$e$$$ not in $$$S$$$, $$$f(S \cup {e}) > f(S)$$$, but it took me a bit of time to realize (and prove) that $$$e_1 > e_2 \implies f(S \cup {e_1}) > f(S \cup {e_2})$$$, which made the problem very nice and easy.

#include <bits/stdc++.h>
#define int ll
#undef BALBIT
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 5e5+5;

struct edge{
    int v, u, i;
};

int bot[maxn]; // bottom node of each edge
int par[maxn]; // parent of node
int L[maxn],R[maxn];
int IT = 0;
vector<edge> g[maxn];

void dfs(int v, int p) {
    par[v] = p;
    L[v] = R[v] = IT++;
    for (edge e : g[v]) {
        if (e.u != p) {
            bot[e.i] = e.u;
            dfs(e.u, v);
            R[v] = R[e.u];
        }
    }
}

vector<edge> E;

int dpar[maxn];
int find(int x) {return x == dpar[x]?x : dpar[x] = find(dpar[x]);}
void mrg(int a, int b) {
    a=find(a); b = find(b);
    dpar[a] = b;
}

int s[maxn];
int QU(int e) {
    int re = 0;
    for (++e; e>0; e-=e&-e) {
        re ^= s[e];
    }
    return re;
}

inline bool isanc(int a, int b) {
    return L[a] <= L[b] && R[a] >= R[b];
}

void MO(int e, int v) {
    for (++e; e<maxn; e+=e&-e) {
        s[e] ^= v;
    }
}

vector<edge> lft;
bool intree[maxn];

int get(int id, ll k) { // k = 1 => find the cheapest
    bug(id);
    if (k > (1ll<<min(SZ(lft), 62ll))) {
        return -1;
    }
    --k; // now change to binary rep
    if (intree[id]) {
        int bt = bot[id];
        int re = QU(R[bt]) ^ QU(L[bt]-1);
        REP(j, min(62ll, SZ(lft))) {
            if (k & (1ll<<j)) {
                re ^= isanc(bt, lft[j].u);
                re ^= isanc(bt, lft[j].v);
            }
        }
        return re;
    }else{
        REP(j, min(62ll, SZ(lft))) {
            if (k & (1ll<<j)) {
                if (lft[j].i == id) return 1;
            }
        }
        return 0;
    }
}

signed main(){
    IOS();
    int n,m; cin>>n>>m;
    REP(i,n) dpar[i] = i;
    bool totpar = 0;
    REP(i,m) {
        int a,b; cin>>a>>b; --a; --b;
        E.pb({a,b,i});
        if (find(a) != find(b)) {
            mrg(a,b);
            g[a].pb(E.back());
            g[b].pb({b,a,i});
            intree[i] = 1;
        }else {
            lft.pb(E.back());
        }
    }
    dfs(0, -1);
    REP(i,n) {
        int p; cin>>p;
        MO(L[i], p); // don't forget L[i]!!!
    }

    ll K; cin>>K;

    REP(i,m) {
        cout<<get(i, K)<<' ';
    }

    cout<<endl;

    int q; cin>>q;
    while (q--) {
        char c; cin>>c;
        if (c == 'M') {
            int v; cin>>v;
            --v; MO(L[v], 1);
            totpar ^= 1;
        }else if (c == 'K') {
            cin>>K;
        }else{
            int i; cin>>i; --i;
            if (totpar == 1) cout<<-1<<endl;
            else cout<<get(i,K)<<endl;
        }
    }


}

I thought this was a nice problem, although not a very hard one (?) Maybe I've seen too many of these "The answer contains at least X% of the set" :P

At first I wasn't sure if O(N^2 * M / 64) * 20 reps would pass, but with a couple of /2s it runs really comfortably in around 0.5s.

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 1e5+5;

int d[1005][202];
bitset<200> so[1005];
int R[1005];

int from[1005], dp[1005];


signed main(){
    IOS();

    mt19937 rnd(time(0));

    int n,m; cin>>n>>m;
    --m;
    REP(i,n) {
        int r; cin>>r; R[i] = r;
        REP(j,m) {
            cin>>d[i][j]; d[i][j] -= r;
        }
    }
    const int MAGIC = 20;

    int bst = 0;
    vector<int>re;

    REP(qqq, MAGIC) {
        int T = rnd()%n;
        vector<int> same;
        vector<pii> gv, lv;
        REP(i,n) {
            if (i == T) {
                same.pb(i); continue;
            }
            int gr = 0;
            int cnt = 0;
            REP(j,m) {
                so[i][j] = 0;
                if (d[i][j] == d[T][j]) continue;
                if (abs(d[i][j] - d[T][j]) >= 2) goto die;

                so[i][j] = 1; ++cnt;
                if (d[i][j] > d[T][j]) {
                    if (gr == -1) goto die;
                    gr = 1;
                }else{
                    if (gr == 1) goto die;
                    gr = -1;
                }
            }

            if (gr == 0) {
                same.pb(i);
            }else if (gr > 0) {
                gv.pb({cnt,i});
            }else{
                lv.pb({cnt,i});
            }
            die:;
        }
        if (SZ(gv) + SZ(lv) + SZ(same) < bst) continue;
        bug(T, bst, SZ(gv), SZ(lv), SZ(same));
        sort(ALL(gv)); sort(ALL(lv));

        memset(from, -1, sizeof from);

        REP(i, SZ(gv)) {
            int it = gv[i].s;
            dp[it] = 1;
            REP(j, i) {
                if (dp[gv[j].s] + 1 > dp[it] && (so[it] | so[gv[j].s]) == so[it]) {
                    dp[it] = dp[gv[j].s] + 1;
                    from[it] = gv[j].s;
                }
            }
        }


        REP(i, SZ(lv)) {
            int it = lv[i].s;
            dp[it] = 1;
            REP(j, i) {
                if (dp[lv[j].s] + 1 > dp[it] && (so[it] | so[lv[j].s]) == so[it]) {
                    dp[it] = dp[lv[j].s] + 1;
                    from[it] = lv[j].s;
                }
            }
        }

        int btog = 0;
        int bg = -1, bl = -1;
        for (pii G : gv) {
            if (dp[G.s] > btog) {
                btog = dp[G.s]; bg = G.s; bl = -1;
            }
        }
        for (pii L : lv) {
            if (dp[L.s] > btog) {
                btog = dp[L.s]; bl = L.s; bg = -1;
            }
        }
        for (pii G : gv) for (pii L : lv) {
            if (dp[G.s] + dp[L.s] > btog && ((so[G.s] & so[L.s]).count() == 0)) {
                btog = dp[G.s] + dp[L.s];
                bg = G.s; bl = L.s;
            }
        }

        if (btog + SZ(same) > bst) {
            vector<pair<pii, int> > rat;
            int stp = 100000;
            for (int at = bg; at != -1; at = from[at]) {
                rat.pb({{R[at], stp}, at});
                --stp;
            }
            stp = -100000;
            for (int at = bl; at != -1; at = from[at]) {
                rat.pb({{R[at], stp},at});
                ++stp;
            }

            for (int t : same) {
                rat.pb({{R[t], 0},t});
            }

            sort(ALL(rat)); reverse(ALL(rat));

            assert(SZ(rat) == btog + SZ(same));

            bst = SZ(rat); re.clear();

            for (auto e : rat) {
                re.pb(e.s+1);
            }
        }

    }

    cout<<SZ(re)<<endl;

    for (int x : re) cout<<x<<' ';
    cout<<endl;

}


/*
4 4
3 3 3 4
3 4 4 4
3 3 4 4
4 4 4 4
*/