oj.uz

Submission #262017

# Submission time Handle Problem Language Result Execution time Memory
262017 2020-08-12T09:32:43 Z lyc Colors (RMI18_colors) C++14
22 / 100
 3000 ms 11520 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 {
	vector<int> p, s;
	vector<ii> history;
	
	void init() {
		p.resize(N+1);
		s.resize(N+1);
		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 = p[i], y = p[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){ cin >> A[i]; }
		FOR(i,1,N){ cin >> B[i]; }
		
		FOR(i,1,N){
			al[i].clear();
			atA[i].clear();
			atB[i].clear();
		}
		
		FOR(i,1,M){
			int U, V; cin >> U >> V;
			al[U].push_back(V);
			al[V].push_back(U);
		}
		
		ok = 1;
		vector<Update> upd;
		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(x _ y _ u _ v);
				if (x <= y) upd.push_back({ x, y, u, v });
			}
			atA[A[u]].push_back(u);
			atB[B[u]].push_back(u);
		}
		
		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 113 ms 11000 KB Output is correct
2 Correct 44 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 111 ms 11364 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 11000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 11000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 11000 KB Output is correct
2 Correct 44 ms 11128 KB Output is correct
3 Correct 14 ms 11520 KB Output is correct
4 Incorrect 126 ms 11000 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 241 ms 11008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3070 ms 11136 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 11000 KB Output is correct
2 Correct 44 ms 11128 KB Output is correct
3 Correct 14 ms 11520 KB Output is correct
4 Correct 111 ms 11364 KB Output is correct
5 Incorrect 126 ms 11000 KB Output isn't correct
6 Halted 0 ms 0 KB -