Submission #262029

#	Time	Username	Problem	Language	Result	Execution time	Memory
262029		lyc	Colors (RMI18_colors)	C++14	100 / 100	693 ms	122972 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;

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

struct UFDS {
	int p[mxN], s[mxN];
	vector<ii> history;
	
	void init() {
		FOR(i,1,N){ p[i] = i; s[i] = 1; }
		history.clear();
	}
	
	int finds(int i) { return (p[i] == i) ? i : finds(p[i]); }
	
	bool unions(int i, int j) {
		int x = finds(i), y = finds(j);
		if (x == y) return 0;
		if (s[x] < s[y]) swap(x,y);
		p[y] = x;
		s[x] += s[y];
		history.emplace_back(x,y);
		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;
			s[x] -= s[y];
			p[y] = y;
		}
	}
} ufds;

struct Update { int x, y, u, v; };
bool ok;

void dnc(int L, int R, vector<Update>& upd) {
	if (L > R) return;
	
	int t = ufds.getTime();
	vector<Update> ul, ur;
	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});
	}
	
	if (L == R) {
		set<int> s;
		for (int& x : atA[L]) s.insert(ufds.finds(x));
		for (int& x : atB[L]) ok &= (s.find(ufds.finds(x)) != s.end());
	} else {
		dnc(L,m,ul);
		dnc(m+1,R,ur);
	}
	
	//~ TRACE(L _ R _ t _ ufds.getTime());
	//~ for (auto& u : upd) { if (L == u.x && R == u.y) cout << u.u _ u.v << " :: "; }
	//~ cout << endl;
	
	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){
			al[i].clear();
			atA[i].clear();
			atB[i].clear();
		}
		
		FOR(i,1,N){ cin >> A[i]; atA[A[i]].push_back(i); }
		FOR(i,1,N){ cin >> B[i]; atB[B[i]].push_back(i); }
		
		vector<Update> upd;
		FOR(i,1,M){
			int U, V; cin >> U >> V;
			int x = max(B[U],B[V]), y = min(A[U],A[V]);
			if (x <= y) upd.push_back({ x, y, U, V });
		}
		
		ok = 1;
		FOR(u,1,N) if (A[u] < B[u]) { ok = 0; break; }
		
		if (ok) {
			ufds.init();
			dnc(1,N,upd);
		}
		cout << ok << '\n';
	}
}

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