Submission #201846

#	Time	Username	Problem	Language	Result	Execution time	Memory
201846		dennisstar	Collapse (JOI18_collapse)	C++17	0 / 100	286 ms	13916 KiB

collapse

#include <bits/stdc++.h>
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
using namespace std;
typedef vector<int> vim;
typedef pair<int, int> pii;
typedef shared_ptr<vector<pii> > pvii;
#include "collapse.h"

const int B = 300;

struct UF {
	vim par, ch; bool im;
	UF(int n, bool i) : par(n, -1), im(i) {}
	int get(int x) { return par[x]!=-1?(par[x]=get(par[x])):x; }
	bool Union(int x, int y) {
		x=get(x), y=get(y);
		if (x!=y) {
			if (im) ch.eb(y);
			par[y]=x;
			return true;
		}
		return false;
	}
	void resolve() { for (auto &i:ch) par[i]=-1; ch.clear(); }
};

vector<pii> solve(int N, vector<pii> Fix, vector<pair<pii, pvii> > S) {
	UF U1(N, false), U2(N, true); vector<pii> R;
	sort(all(Fix), [](pii &p1, pii &p2){ return p1.se<p2.se; });
	sort(all(S), [](pair<pii, pvii> &p1, pair<pii, pvii> &p2){ return p1.fi.fi<p2.fi.fi; });
	int tp=0, cnt=0;
	for (auto &i:S) {
		for (; tp<Fix.size()&&Fix[tp].se<=i.fi.fi; tp++) cnt+=U1.Union(Fix[tp].fi, Fix[tp].se);
		int im=cnt;
		for (auto &j:*i.se) if (j.se<=i.fi.fi) im+=U2.Union(U1.get(j.fi), U1.get(j.se));
		R.eb(i.fi.se, i.fi.fi+1-im);
		U2.resolve();
	}
	return R;
}

vim simulateCollapse(int N, vim T, vim X, vim Y, vim W, vim P) {
	int D=T.size(), Q=W.size();
	vim A(Q, 0); set<pii> Fix;
	vector<pair<pii, int> > qu;
	for (int i=0; i<Q; i++) qu.eb(pii(W[i], P[i]), i); sort(all(qu));
	for (int i=0; i<D; i++) if (X[i]>Y[i]) swap(X[i], Y[i]);
	for (int s=0, tp=0; s<D; s+=B) {
		int e=min(D, s+B);
		set<pii> nFix;
		for (int i=s; i<e; i++) if (Fix.find(pii(X[i], Y[i]))!=Fix.end())
			Fix.erase(pii(X[i], Y[i])), nFix.em(X[i], Y[i]);
		vector<pair<pii, pvii> > S1, S2;
		for (int i=s; i<e; i++) {
			if (T[i]==1) nFix.erase(pii(X[i], Y[i]));
			if (T[i]==0) nFix.em(X[i], Y[i]);
			pvii nf1(new vector<pii>), nf2(new vector<pii>);
			for (auto &j:nFix) nf1->eb(j), nf2->eb(N-1-j.se, N-1-j.fi);
			for (; tp<Q&&qu[tp].fi.fi==i; tp++)
				S1.eb(pii(qu[tp].fi.se, qu[tp].se), nf1), S2.eb(pii(N-2-qu[tp].fi.se, qu[tp].se), nf2);
		}
		vector<pii> F1, F2;
		for (auto &i:Fix) F1.eb(i), F2.eb(N-1-i.se, N-1-i.fi);
		vector<pii> r1 = solve(N, F1, S1);
		vector<pii> r2 = solve(N, F2, S2);
		for (auto &i:r1) A[i.fi]+=i.se;
		for (auto &i:r2) A[i.fi]+=i.se;
		for (int i=s; i<e; i++) {
			if (T[i]==0) Fix.erase(pii(X[i], Y[i]));
			if (T[i]==1) Fix.em(X[i], Y[i]);
		}
	}
	return A;
}

Compilation message (stderr)

collapse.cpp: In function 'std::vector<std::pair<int, int> > solve(int, std::vector<std::pair<int, int> >, std::vector<std::pair<std::pair<int, int>, std::shared_ptr<std::vector<std::pair<int, int> > > > >)':
collapse.cpp:37:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; tp<Fix.size()&&Fix[tp].se<=i.fi.fi; tp++) cnt+=U1.Union(Fix[tp].fi, Fix[tp].se);
          ~~^~~~~~~~~~~
collapse.cpp: In function 'vim simulateCollapse(int, vim, vim, vim, vim, vim)':
collapse.cpp:50:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (int i=0; i<Q; i++) qu.eb(pii(W[i], P[i]), i); sort(all(qu));
  ^~~
collapse.cpp:50:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int i=0; i<Q; i++) qu.eb(pii(W[i], P[i]), i); sort(all(qu));
                                                     ^~~~

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