Submission #272816

#	Time	Username	Problem	Language	Result	Execution time	Memory
272816		limabeans	Collapse (JOI18_collapse)	C++17	5 / 100	15050 ms	28752 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;
}


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]});
    }
    vector<line> v;
    for (int i=0; i<n; i++) {
	v.push_back({T[i],X[i],Y[i]});
    }

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

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