Submission #1012954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012954		Cookie	Collapse (JOI18_collapse)	C++14	100 / 100	4633 ms	235040 KiB

collapse

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,tune=native")
//huhu
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
#define ull unsigned long long
const int mxn = 1e5 + 5, inf = 1e9 + 5, sq = 350;
 
#include "collapse.h"
int n;
struct DSU{
    int pa[mxn + 1];
    vt<int>comp;
    void init(){
        for(int i = 0; i < n; i++)pa[i] = -1;
    }
    int fp(int u){
        if(pa[u] < 0)return(u);
        return(pa[u] = fp(pa[u]));
    }
    bool unon(int u, int v){
        comp.pb(u); comp.pb(v);
        u = fp(u); v = fp(v);
        if(u == v)return(0);
        if(-pa[u] < -pa[v])swap(u, v);
        pa[u] += pa[v]; pa[v] = u;
        return(1);
    }
    void reset(){
        for(auto i: comp){
            pa[i] = -1;
        }
        comp.clear();
    }
};
struct Q{
    int tme, p, id;
    bool operator <(const Q &other){
        return(p < other.p);
    }
};
vt<Q>queries;
bool cmpl(pii a, pii b){
    return(a.se < b.se);
}
bool cmpr(pii a, pii b){
    return(a.fi > b.fi);
}
vt<int>t, x, y, w, p, res;
set<pair<int, int>>all; // edges after block[i - 1]
vt<pii>inblock[mxn + 1]; // edges that appear in block
void solve(int l, int r){
    set<pair<int, int>>remain = all;
    for(int i = l; i <= r; i++){
        if(t[i] == 1 && remain.count(mpp(x[i], y[i]))){
            remain.erase(mpp(x[i], y[i]));
        }
    }
    
    map<pair<int, int>, int>last;
    for(int i = l; i <= r; i++){
        if(t[i] == 0){
            assert(last.find(mpp(x[i], y[i])) == last.end());
            last[mpp(x[i], y[i])] = i;
        }else{
            int lt = ((last.find(mpp(x[i], y[i])) == last.end()) ? l : last[mpp(x[i], y[i])]);
            for(int j = lt; j < i; j++){
                inblock[j].pb(mpp(x[i], y[i]));
            }
            last.erase(mpp(x[i], y[i]));
        }
    }
    
    for(auto i: last){
        for(int j = i.se; j <= r; j++){
            inblock[j].pb(i.fi);
        }
    }
    vt<pii>edge;
    for(auto i: remain)edge.pb(i);
    sort(ALL(edge), cmpl);
    vt<Q>curr;
    for(auto i: queries){
        if(i.tme >= l && i.tme <= r){
            curr.pb({i.tme, i.p, i.id});
        }
    }
    sort(ALL(curr));
    int lp = 0;
    DSU dsu, dsu2; dsu.init();  dsu2.init();
    int cnt = 0; //global connection 
    for(auto [tme, pl, id]: curr){
        while(lp < sz(edge) && edge[lp].se <= pl){
            cnt += dsu.unon(edge[lp].fi, edge[lp].se); lp++;
        }
        int cnt2 = cnt; // connection for this query only 
        for(auto [u, v]: inblock[tme]){
            if(v <= pl){
                cnt2 += dsu2.unon(dsu.fp(u), dsu.fp(v));
            }
        }
        dsu2.reset();
        res[id] += (pl) - cnt2;
    }
    dsu.init(); dsu2.init();
    curr.clear();
    // same thing but for right side :>
    for(auto i: queries){
        if(i.tme >= l && i.tme <= r){
            curr.pb({i.tme, i.p + 1, i.id});
        }
    }
    sort(ALLR(curr));
    sort(ALL(edge), cmpr);
    int rp = 0;
    cnt = 0; //global connection 
    for(auto [tme, pr, id]: curr){
        while(rp < sz(edge) && edge[rp].fi >= pr){
            cnt += dsu.unon(edge[rp].fi, edge[rp].se); rp++;
        }
        int cnt2 = cnt; // connection for this query only 
        for(auto [u, v]: inblock[tme]){
            if(u >= pr){
                cnt2 += dsu2.unon(dsu.fp(u), dsu.fp(v));
            }
        }
        dsu2.reset();
        res[id] += (n - pr + 1) - cnt2;
    }
    for(int i = l; i <= r; i++){
        if(t[i] == 0)all.insert(mpp(x[i], y[i]));
        else all.erase(mpp(x[i], y[i]));
    }
    
}

std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) {
    n = N; t = T; x = X; y = Y; w = W; p = P;
    for(int i = 0; i < sz(x); i++){
        if(x[i] > y[i])swap(x[i], y[i]);
    }
    for(int i = 0; i < sz(w); i++){
        queries.pb({w[i], p[i], i});
    }
    res.resize(sz(queries));
	int l = 0;
	for(int i = 0; i < sz(t); i += sq){
	    solve(i, min(i + sq - 1, sz(t) - 1));
	}
	return(res);
}
 
 /*
int main(int argc, char *argv[]) {
	int N, C, Q;
	scanf("%d%d%d", &N, &C, &Q);
	std::vector<int> T(C), X(C), Y(C);
	for(int i = 0; i < C; i++) {
		scanf("%d%d%d", &T[i], &X[i], &Y[i]);
	}
	std::vector<int> W(Q), P(Q);
	for(int i = 0; i < Q; i++) {
		scanf("%d%d", &W[i], &P[i]);
	}
	auto res = simulateCollapse(N, T, X, Y, W, P);
	for(auto i : res) {
		printf("%d\n", i);
	}
}
*/

Compilation message (stderr)

collapse.cpp: In function 'void solve(int, int)':
collapse.cpp:108:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |     for(auto [tme, pl, id]: curr){
      |              ^
collapse.cpp:113:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |         for(auto [u, v]: inblock[tme]){
      |                  ^
collapse.cpp:133:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  133 |     for(auto [tme, pr, id]: curr){
      |              ^
collapse.cpp:138:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |         for(auto [u, v]: inblock[tme]){
      |                  ^
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:169:6: warning: unused variable 'l' [-Wunused-variable]
  169 |  int l = 0;
      |      ^

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35