Submission #272925

#	Time	Username	Problem	Language	Result	Execution time	Memory
272925		limabeans	Collapse (JOI18_collapse)	C++17	35 / 100	15061 ms	29328 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl


struct dsu0 {
    vector<int> par, siz;
    int n;
    int cc;
    int largest;
    void init(int n) {
	assert(n>0);
	this->n=n;
	cc=n;
	par.resize(n+10);siz.resize(n+10);
	for (int i=0; i<n; i++) par[i]=i,siz[i]=1;
	largest=1;
    }
    int parent(int x) {
	assert(x>=0 && x<n);
	return par[x]==x?x:par[x]=parent(par[x]);
    }
    bool join(int x, int y) {
	x=parent(x);y=parent(y);
	if (x==y) return false;
	cc--;
	if (siz[x]<siz[y]) swap(x,y);
	siz[x]+=siz[y];par[y]=x;
	largest=max(largest,siz[x]);
	return true;
    }
};


using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e5 + 5;

struct line {
    int type, x, y;
    line(int _t, int _x, int _y) : type(_t), x(_x), y(_y) {}
};


set<int> g[maxn];
set<pair<int,int>> edges;


void add_edge(int x, int y) {
    if (x>y) swap(x,y);
    g[x].insert(y);
    g[y].insert(x);
    edges.insert({x,y});
}

void rem_edge(int x, int y) {
    if (x>y) swap(x,y);
    g[x].erase(y);
    g[y].erase(x);
    edges.erase({x,y});
}

vector<int> solve(int N, vector<line> v, vector<vector<pair<int,int>>> ev, int Q) {
    int n = v.size();
    vector<int> ans(Q);

    for (int i=0; i<n; i++) {
	if (v[i].type==0) {
	    add_edge(v[i].x,v[i].y);
	} else {
	    rem_edge(v[i].x,v[i].y);
	}

	for (auto qu: ev[i]) {
	    int id = qu.first;
	    int x = qu.second;
	    dsu0 dsu; dsu.init(N);
	    for (auto ed: edges) {
		int u = ed.first;
		int v = ed.second;
		if (u<=x && x+1<=v) continue;
		dsu.join(u,v);
	    }
	    ans[id] = dsu.cc;
	}
    }
    return ans;
}



struct dsu_rollback {
    int n;
    vector<int> par, siz;
    int cc;
    vector<pair<int,int>> undo;
    
    void init(int n) {
	this->n=n;
	par.resize(n);
	siz.resize(n);
	for (int i=0; i<n; i++) {
	    par[i]=i;
	    siz[i]=1;
	}
	cc = n;
    }
    int parent(int x) {
	while (par[x] != x) x=par[x];
	return x;
    }

    void join(int u, int v) {
	u = parent(u);
	v = parent(v);
	if (u != v) {
	    if (siz[u]<siz[v]) swap(u,v);
	    par[v]=u;
	    siz[u]+=siz[v];
	    cc--;
	}
	undo.push_back({u,v});
    }

    void rollback() {
	assert(undo.size());
	int u = undo.back().first;
	int v = undo.back().second;
	if (u!=v) {
	    siz[u]-=siz[v];
	    par[v]=v;
	    cc++;
	}
	undo.pop_back();
    }
};


const int SQ = 316; // sqrt(10^5) = 316.227

struct dat {
    int x, y, id;
    dat(int _x, int _y, int _id) : x(_x), y(_y), id(_id) {}
};



bool cmpY(dat A, dat B) {
    if (A.y != B.y) return A.y < B.y;
    return A.id < B.id;
}

bool cmpX(dat A, dat B) {
    if (A.x != B.x) return A.x > B.x;
    return A.id < B.id;
}

// All lines in v are addEdge(x,y)
// requests[time]: idx, loc
vector<int> solveTask3(int N, vector<line> v, vector<vector<pair<int,int>>> requests, int Q) {
    //cerr<<"task3"<<endl;
    int m = v.size();
    for (auto &line: v) {
	if (line.x>line.y) {
	    swap(line.x,line.y);
	}
    }
    vector<int> reqTime(Q);
    for (int i=0; i<m; i++) {
	for (auto p: requests[i]) reqTime[p.first] = i;
    }
    vector<int> ans(Q, -N);
    vector<int> alive;

    // iterate over sqrt blocks of time
    for (int i=0; i<m; i+=SQ) {
	int start = i; int end = min(i+SQ-1, m-1);
	// [start, end]
	vector<dat> op;

	// sort by increasing Y
	{
	    op.clear();
	    // add all alive graph edits
	    for (int idx: alive) {
		op.push_back({v[idx].x,v[idx].y,-1});
	    }
	    // add all relevant queries
	    for (int j=start; j<=end; j++) {
		for (auto p: requests[j]) {
		    op.push_back({p.second,p.second,p.first});
		}
	    }

	    
	    sort(op.begin(), op.end(), cmpY);
	    dsu_rollback dsu;
	    dsu.init(N);
	    for (auto o: op) {
		if (o.id < 0) {
		    dsu.join(o.x,o.y);
		} else {
		    int time = reqTime[o.id];
		    int did = 0;
		    for (int j=start; j<=time; j++) {
			if (v[j].y<=o.x) {
			    dsu.join(v[j].x,v[j].y);
			    did++;
			}
		    }
		    ans[o.id] += dsu.cc;
		    while (did--) {
			dsu.rollback();
		    }
		}
	    }
	}


	// sort by decreasing X
	{
	    op.clear();
	    // add all alive graph edits
	    for (int idx: alive) {
		op.push_back({v[idx].x,v[idx].y,-1});
	    }
	    // add all relevant queries
	    for (int j=start; j<=end; j++) {
		for (auto p: requests[j]) {
		    op.push_back({p.second+1,p.second+1,p.first});
		}
	    }

	    
	    sort(op.begin(), op.end(), cmpX);
	    dsu_rollback dsu;
	    dsu.init(N);
	    for (auto o: op) {
		if (o.id < 0) {
		    dsu.join(o.x,o.y);
		} else {
		    int time = reqTime[o.id];
		    int did = 0;
		    for (int j=start; j<=time; j++) {
			if (o.y<=v[j].x) {
			    dsu.join(v[j].x,v[j].y);
			    did++;
			}
		    }
		    ans[o.id] += dsu.cc;
		    while (did--) {
			dsu.rollback();
		    }
		}
	    }
	}


	// update alive
	for (int j=start; j<=end; j++) {
	    alive.push_back(j);
	}
    }

    return ans;
}



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
				  ) {

    int n = T.size();
    
    vector<vector<pair<int,int>>> ev(n);
    for (int i=0; i<(int)W.size(); i++) {
	ev[W[i]].push_back({i,P[i]});
    }

    bool t0 = true;
    vector<line> v;
    for (int i=0; i<n; i++) {
	v.push_back({T[i],X[i],Y[i]});
	if (T[i]==1) t0=false;
    }

    if (t0) return solveTask3(N, v, ev, W.size());

    return solve(N, v, ev, W.size());
}

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