oj.uz

Submission #262029

# Submission time Handle Problem Language Result Execution time Memory
262029 2020-08-12T09:43:48 Z lyc Colors (RMI18_colors) C++14
100 / 100
 693 ms 122972 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 11008 KB Output is correct
2 Correct 48 ms 11128 KB Output is correct
3 Correct 14 ms 11520 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 11240 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 11000 KB Output is correct
2 Correct 63 ms 11008 KB Output is correct
3 Correct 14 ms 11136 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 11000 KB Output is correct
2 Correct 63 ms 11008 KB Output is correct
3 Correct 14 ms 11136 KB Output is correct
4 Correct 261 ms 11008 KB Output is correct
5 Correct 537 ms 28864 KB Output is correct
6 Correct 693 ms 55348 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 11008 KB Output is correct
2 Correct 48 ms 11128 KB Output is correct
3 Correct 14 ms 11520 KB Output is correct
4 Correct 131 ms 11000 KB Output is correct
5 Correct 63 ms 11008 KB Output is correct
6 Correct 14 ms 11136 KB Output is correct
7 Correct 125 ms 11008 KB Output is correct
8 Correct 50 ms 11008 KB Output is correct
9 Correct 15 ms 11392 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 11140 KB Output is correct
2 Correct 486 ms 33120 KB Output is correct
3 Correct 441 ms 38248 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 11180 KB Output is correct
2 Correct 24 ms 11604 KB Output is correct
3 Correct 15 ms 11196 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 11008 KB Output is correct
2 Correct 48 ms 11128 KB Output is correct
3 Correct 14 ms 11520 KB Output is correct
4 Correct 98 ms 11240 KB Output is correct
5 Correct 131 ms 11000 KB Output is correct
6 Correct 63 ms 11008 KB Output is correct
7 Correct 14 ms 11136 KB Output is correct
8 Correct 261 ms 11008 KB Output is correct
9 Correct 537 ms 28864 KB Output is correct
10 Correct 693 ms 55348 KB Output is correct
11 Correct 125 ms 11008 KB Output is correct
12 Correct 50 ms 11008 KB Output is correct
13 Correct 15 ms 11392 KB Output is correct
14 Correct 238 ms 11140 KB Output is correct
15 Correct 486 ms 33120 KB Output is correct
16 Correct 441 ms 38248 KB Output is correct
17 Correct 53 ms 11180 KB Output is correct
18 Correct 24 ms 11604 KB Output is correct
19 Correct 15 ms 11196 KB Output is correct
20 Correct 143 ms 13768 KB Output is correct
21 Correct 472 ms 39004 KB Output is correct
22 Correct 691 ms 122972 KB Output is correct