Submission #590522

#	Time	Username	Problem	Language	Result	Execution time	Memory
590522		balbit	Reconstruction Project (JOI22_reconstruction)	C++14	100 / 100	2968 ms	36792 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define pb push_back


#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__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 bug(...)
#define endl '\n'
#endif // BALBIT

//const int maxn = 3e5+5;
const int MXM = 1e5+5;
const int MXN = 502;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int eA[MXM], eB[MXM], eW[MXM];
int n,m;
vector<int> g[MXN];
ll best[MXN];

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

vector<int> curedges;
pii mst(){
    REP(i,n) par[i] = i;
    pii re = {curedges.back(), -1};
    int gone = -1;
    for (int i = SZ(curedges)-1; i >= 0; --i) {
        int e = curedges[i];
        if (find(eA[e]) != find(eB[e])) {
            mrg(eA[e], eB[e]);
        }else {
            re.s = e;
            gone = i;
        }
    }
    if (gone != -1) {
        curedges.erase(curedges.begin() + gone);
    }
    return re;
}

vector<int> gA, gB;

//bool used[maxn];

//ll mst2(int T){
//    ll re = 0;
//    int i = SZ(gA)-1, j = SZ(gB)-1;
//    while (i>=0 || j>=0) {
//        if (i==-1 || (j!=-1 && eW[gB]))
//    }
//}

int L[MXM],R[MXM];

void get(vector<int> eid, bool workl) {
    // for each added edge (in order), find the mst change
//    vector<pii> re; // {added edge, removed edge}; -1 if no change
    curedges.clear();
    REP(i, SZ(eid)) {
        curedges.pb(eid[i]);
        pii get = mst();
        int bye = get.s;
        if (bye != -1) {
            if (workl) {
                L[bye] = (eW[get.s] + eW[eid[i]]) / 2 + 1;
            }else{
                R[bye] = (eW[get.s] + eW[eid[i]]) / 2 + 1;
            }
        }
    }
}

//bool inuse[MXM];

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(__lg(25)+1);

    cin>>n>>m;
//    bug(get(n,m));

    vector<int> eid;
    REP(i,m) {
        int a,b,w; cin>>a>>b>>w; --a; --b;
        eA[i] = a, eB[i] = b, eW[i] = w;
        eid.pb(i);
    }

    sort(ALL(eid), [&](int a, int b){return make_pair(eW[a],a) < make_pair(eW[b],b);});

//    vector<pii> chga = get(eid);
//    reverse(ALL(eid));
//    vector<pii> chgb = get(eid);
//    reverse(ALL(chgb));
//    reverse(ALL(eid));

    memset(L, -1, sizeof L);
    memset(R, 0x3f, sizeof R);

    get(eid, 0);
    reverse(ALL(eid));
    get(eid, 1);
    reverse(ALL(eid));


    for (int e : curedges) {
        bug(e, eA[e], eB[e], eW[e]);
    }

    vector<pair<int, pii> > event;

    REP(i,m) {
        bug(i, eA[i], eB[i], eW[i]);
        bug(L[i], R[i]);
        event.pb({L[i], {eW[i], -1}});
        event.pb({eW[i], {-2*eW[i], 2}});
        event.pb({R[i], {eW[i], -1}});
    }

    int Q; cin>>Q;
    int eat = 0;
//    mst2();
    sort(ALL(event));
    vector<int> now;

    ll fm =0, fb = 0; // mT + b

    while (Q--) {
        int T; cin>>T;
        while (eat < SZ(event) && event[eat].f <= T) {
            fm += event[eat].s.s;
            fb += event[eat].s.f;
            ++eat;
        }

        bug(fm, fb, T);
        cout<<fm * T + fb<<endl;

//        bool madechg = 0;
//        while (eat < SZ(eid) && T >= eW[eid[eat]]) {
//
//            if (chga[eat].s!=-1) gA.erase(find(ALL(gA), chga[eat].s));
//            if (chga[eat].f!=-1) gA.pb(chga[eat].f);
//
//            if (chgb[eat].f!=-1) gB.erase(find(ALL(gB), chgb[eat].f));
//            if (chgb[eat].s!=-1) {
//                gB.pb(chgb[eat].s);
//                for (int j = SZ(gB)-1; j>0 && eW[gB[j]] > eW[gB[j-1]]; --j) {
//                    swap(gB[j], gB[j-1]);
//                }
//            }
//
//            ++eat;
//            madechg = 1;
//        }
//        if (madechg) {
//            mst2();
//        }


    }


}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:132:14: warning: unused variable 'e' [-Wunused-variable]
  132 |     for (int e : curedges) {
      |              ^

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23