Submission #1138445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138445		dadas08	Colors (RMI18_colors)	C++20	0 / 100	138 ms	150164 KiB

colors

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
// #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
void _main();
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	_main();
	return 0;
}
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vl = std::vector<ll>;
using vii = std::vector<pair<int, int> >;
using vvl = std::vector<vl>;
using vll = std::vector<pair<ll , ll> >;
using vd = std::vector<double>;
using vvd = std::vector<vd>;
using vs = std::vector<std::string>;
using vvs = std::vector<vs>;
using vb = std::vector<bool>;
using vvb = std::vector<vb>;
using vc = std::vector<char>;
using vvc = std::vector<vc>;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using piil = std::pair<pair<int, int>, ll>;
using mii = std::map<int, int>;
using mll = std::map<ll, ll>;
using pql = std::priority_queue<ll>;
using pqi = std::priority_queue<int>;
using pqiil = std::priority_queue<pair<pair<int, int>, ll> >;
using pqii = std::priority_queue<pair<int, int> >;

#define pb push_back
#define ps push
#define eb emplace_back
#define is insert
#define er erase
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define sf(i) sizeof(i)
#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define rep(i, L, R) for(ll i = L;i<=R;i++)
#define pcis precision
#define sz(a) ((ll) a.size())

template<typename T>
struct infinity {
	static constexpr T max=std::numeric_limits<T>::max();
	static constexpr T min=std::numeric_limits<T>::min();
	static constexpr T value=std::numeric_limits<T>::max()/2;
	static constexpr T mvalue=std::numeric_limits<T>::min()/2;
};
template<typename T>constexpr T INF=infinity<T>::value;
constexpr ll lINF=INF<ll>;
constexpr int iINF = INF<int>;
constexpr ld PI = 3.1415926535897932384626;

struct UnionFindWithRollback {
	int par[300100]; // 루트라면 , -(트리의 크기) 를 저장. 아니라면 부모를 저장
	stack<tuple<int,int,int>> S;
	UnionFindWithRollback() {
		memset(par, -1, sizeof(par));
	}

	// O(log N) // 부모를 찾아 반환함
	int find(int x) {
		if(par[x]<0) return x;
		return find(par[x]);
	}

	// O(log N)
	bool uni(int x, int y) {
		x = find(x), y = find(y);
		if(x == y) return false;// かわらず
		if(par[x] < par[y]) swap(x,y);// x가 항상 더 큼  -> x에 y를 달음
		S.push({x, y, par[x]}); // 역추적
		par[y] += par[x];
		par[x] = y;
		return true;
	}

	// O(1)
	void rollback() {
		int x = get<0>(S.top()), y = get<1>(S.top()), sz = get<2>(S.top());
		par[y] -= sz;
		par[x] = sz;
		S.pop();
	}
};

UnionFindWithRollback UF;

vll tree[6010000]; // 분할정복 과정을 트리로 나타낸 것
vl col[300001];
ll N;

//라이프타임이 s~e인 간선 u-v를 분할-정복 트리의 노드에 추가. (포함되면 추가)
//조건 : l~r에 살아있는, 즉, s <= l && r <= e
void init(int u, int v, int start, int end, int node, int left, int right) {
	if(end < left || right < start) return;
	if(start <= left && right <= end) {
		tree[node].pb({u, v});
		return;
	}
	int mid = (left+right)/2;
	init(u, v, start, end, node*2, left, mid);
	init(u, v, start, end, node*2+1, mid+1, right);
}

bool CAN = true;

void get(int node, int left, int right) {
	ll kawatta = 0;
	for(auto &p : tree[node])
		kawatta += UF.uni(p.f, p.s);// 이 아래로 내려가면 이것들은 공통적으로 있으므로 추가해줌
	//리프에 도달했으면, 현재 구간이 쿼리라면 출력
	if(left == right) {
		for (auto i : col[left]) {
			if (UF.find(i) != UF.find(N + left)) {
				CAN = false;
			}
		}
	}
	if(left != right) {
		// 아래로 재귀
		int mid = (left+right)/2;
		get(node*2, left, mid);
		get(node*2+1, mid+1, right);
	}
	//롤백
	while(kawatta--)
		UF.rollback();
}

//
//void solve() {
//
//	int N, M;
//	cin >> N >> M;
//	for(int i=0; i<M; ++i) {
//		for (int j = 0; j < 3; ++j)
//			cin >> query[i][j];
//		if(query[i][1] > query[i][2])
//			swap(query[i][1], query[i][2]);
//	}
//	map<pii, int> ikiru; // 각 간선이 생존해있는 시간
//	for(int i=0; i<M; ++i) {
//		int &u = quer1y[i][1], &v = query[i][2];
//		if(query[i][0] == 1) { //간선 추가
//			ikiru[ {u, v}] = i;// i부터 살기 시작함
//		} else if(query[i][0] == 2) { //간선 삭제
//			int s = ikiru[ {u, v}];// s ~ i까지 살음
//			init(u, v, s, i, 1, 0, M-1);// 간선을 트리에 박음
//			ikiru.erase({u, v});// 그리고 D짐
//		}
//	}
//	for(auto &p : ikiru) {
//		int u = p.f.f, v = p.f.s, s = p.s;
//		init(u, v, s, M-1, 1, 0, M-1);// 남은건 싹다 끝까지 산거임
//	}
//	get(1, 0, M-1);// 풀면 됨
//}

void _main() {

	ll T;
	cin >> T;
	while (T--) {
		ll N, M;
		cin >>N>>M;
		::N = N;
		ll A[N+1], B[N+1];
		CAN = true;
		rep(i,1,N) cin >> A[i];
		rep(i,1,N) cin >> B[i];

		rep(i,0,N*4) tree[i].clear();

		for (ll i = 1; i<=M; i++) {
			ll a, b;
			cin >> a >> b;
			ll left = max(B[a], B[b]);
			ll right = min(A[a], A[b]);
			if (left <= right) init(a-1, b-1, left-1, right-1, 1, 0, N-1);// 저 시간동안에만 쓸 수 있음
		}

		while (!UF.S.empty()) UF.S.pop();

		rep(i,0,N) col[i].clear();
		rep(i,1,N) col[B[i]-1].pb(i-1);

		rep(i,1,N) UF.uni(i-1, N + A[i]-1);// 그 색 -> 그 색을 가지는 친구 (기본으로 이정돈 해둠)
		get(1, 0, N-1);

		cout << CAN << endl;
	}
}

• 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