제출 #261734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
261734		lyc	Colors (RMI18_colors)	C++14	0 / 100	3088 ms	21504 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;
const int inf = 2e5+5;

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

vector<int> atB[mxN];

struct UFDS {
	int p[mxN];
	set<int> s[mxN];
	multiset<int> col[mxN];
	
	UFDS(){
		FOR(i,1,N){
			p[i] = i;
			s[i].insert(i);
			col[i].insert(A[i]);
		}
	}
	
	int finds(int i) { return p[i]; }
	bool unions(int i, int j) {
		int x = finds(i), y = finds(j);
		if (x == -1 || y == -1 || x == y) return 0;
		if (SZ(s[x]) < SZ(s[y])) swap(x,y);
		for (auto& a : s[y]) {
			p[a] = x;
			s[x].insert(a);
		}
		for (auto& a : col[y]) {
			col[x].insert(a);
		}
		return 1;
	}
	
	void rm(int u) {
		int x = finds(u);
		p[x] = -1;
		s[x].erase(u);	// unique
		col[x].erase(col[x].find(A[u]));
	}
	
	bool findCol(int u, int c) {
		int x = finds(u);
		return !!col[x].count(c);
	}
};

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);
		}
		
		FOR(b,1,N) atB[b].clear();
		FOR(u,1,N) atB[B[u]].push_back(u);
		
		UFDS ufds;
		using edge=tuple<int,int,int>;	// priority, from, to
		priority_queue<ii,vector<ii>,greater<ii>> del;
		priority_queue<edge,vector<edge>,greater<edge>> add;
		
		bool ok = 1;
		FOR(b,1,N){
			if (!ok) break;
			for (int& u : atB[b]) {
				del.emplace(A[u], u);
				for (int& v : al[u]) {
					add.emplace(B[v], u, v);
				}
			}
			//~ TRACE("ADDED" _ b);
			while (!del.empty() && del.top().first < b) {
				auto v = del.top(); del.pop();
				ufds.rm(v.second);
			}
			//~ TRACE("REMOVED" _ b);
			while (!add.empty()) {
				auto e = add.top(); 
				int pr, fr, to; tie(pr,fr,to) = e;
				if (pr > b) break;
				add.pop();
				ufds.unions(fr,to);
			}
			//~ TRACE("RELAXED" _ b);
			
			for (int& u : atB[b]) {
				ok &= (ufds.findCol(u, B[u]));
			}
		}
		
		cout << ok << '\n';
	}
}

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