Submission #261755

#	Time	Username	Problem	Language	Result	Execution time	Memory
261755		lyc	Colors (RMI18_colors)	C++14	47 / 100	3060 ms	68372 KiB

colors

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ii=pair<int,int>;

const int mxN = 150005;
//~ const int mxN = 1505;

int N, M, A[mxN], B[mxN];
vector<int> al[mxN];

struct Update {	int x, y, u, v; };
struct Query { int b, u; };

struct UFDS {
	vector<int> p;
	vector<set<int>> s;
	vector<map<int,int>> col;
	
	vector<ii> history;
	
	void init() {
		p.resize(N+1);
		s.resize(N+1);
		col.resize(N+1);
		FOR(i,1,N){
			p[i] = i;
			s[i].clear();
			s[i].insert(i);
			col[i].clear();
			col[i][A[i]] = 1;
		}
	}
	
	bool unions(int i, int j) {
		//~ TRACE("UNIONS" _ i _ j);
		int x = p[i], y = p[j];
		if (x == y) return 0;
		if (SZ(s[x]) < SZ(s[y])) swap(x,y);
		history.emplace_back(x,y);
		for (int a : s[y]) {
			s[x].insert(a);
			++col[x][A[a]];
			p[a] = x;
		}
		return 1;
	}
	
	int getTime() { return SZ(history); }
	void undo(int t) {
		while (SZ(history) > t) {
			ii cur = history.back(); history.pop_back();
			int x = cur.first, y = cur.second;
			for (int a : s[y]) {
				s[x].erase(a);
				--col[x][A[a]];
				p[a] = y;
			}
		}
	}
	
	int query(int i, int c) {
		return col[p[i]][c];
	}
} ufds;

bool reach[mxN];

void dnc(int L, int R, vector<Update> upd, vector<Query> qry) {
	if (L > R) return;
	
	int t = ufds.getTime();
	vector<Update> ul, ur;
	vector<Query> ql, qr;
	int m = (L+R)/2;
	for (auto& u : upd) {
		if (L == u.x && R == u.y) ufds.unions(u.u,u.v);
		else if (u.y <= m) ul.push_back(u);
		else if (u.x > m) ur.push_back(u);
		else ul.push_back({u.x, m, u.u, u.v}), ur.push_back({m+1, u.y, u.u, u.v});
	}
	for (auto& q : qry) {
		if (q.b <= m) ql.push_back(q);
		else qr.push_back(q);
	}
	
	if (L != R) {
		dnc(L,m,ul,ql);
		dnc(m+1,R,ur,qr);
	}
	
	//~ TRACE(L _ R _ t _ ufds.getTime());
	//~ for (auto& u : upd) { if (L == u.x && R == u.y) cout << u.u _ u.v << " :: "; }
	//~ cout << endl;
	for (auto& q : qry) {
		//~ TRACE("QUERY" _ q.u _ q.b _ ufds.query(q.u, q.b));
		reach[q.u] |= ufds.query(q.u, q.b) > 0;
	}
	
	ufds.undo(t);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int TC; cin >> TC;
    while (TC--) {
		cin >> N >> M;
		FOR(i,1,N){ cin >> A[i]; }
		FOR(i,1,N){ cin >> B[i]; }
		
		FOR(i,1,N) al[i].clear();
		FOR(i,1,M){
			int U, V; cin >> U >> V;
			al[U].push_back(V);
			al[V].push_back(U);
		}
	
		bool ok = 1;
		vector<Update> upd;
		vector<Query> qry;
		FOR(u,1,N){
			if (A[u] < B[u]) { ok = 0; break; }
			for (int& v : al[u]) if (u < v) {
				int x = max(B[u],B[v]), y = min(A[u],A[v]);
				//~ TRACE("UPD" _ x _ y _ u _ v);
				if (x <= y) upd.push_back({ x, y, u, v });
			}
			qry.push_back({ B[u], u });
		}
		
		if (ok) {
			memset(reach,0,sizeof reach);
			ufds.init();
			dnc(1,N,upd,qry);
			//~ FOR(i,1,N){ cout << reach[i] << ' '; } cout << endl;
			FOR(i,1,N) ok &= reach[i];
		}
		cout << ok << '\n';
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 0 / 15
• Subtask 5: 7 / 7
• Subtask 6: 0 / 16
• Subtask 7: 10 / 10
• Subtask 8: 0 / 22