oj.uz

Submission #258233

# Submission time Handle Problem Language Result Execution time Memory
258233 2020-08-05T15:08:12 Z Saboon Board (CEOI13_board) C++14
70 / 100
 200 ms 1792 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 4e5 + 10;

int l[maxn], r[maxn], lc[maxn], rc[maxn], par[maxn];
int newint = 2;

void addrc(int v, int u){
	rc[v] = u;
	par[u] = v;

	if (lc[r[v]] != 0){
		l[lc[r[v]]] = u;
		r[u] = lc[r[v]];
	}

	if (lc[v] != 0){
		r[lc[v]] = u;
		l[u] = lc[v];
	}
}

void addlc(int v, int u){
	lc[v] = u;
	par[u] = v;

	if (rc[l[v]] != 0){
		r[rc[l[v]]] = u;
		l[u] = rc[l[v]];
	}

	if (rc[v] != 0){
		l[rc[v]] = u;
		r[u] = rc[v];
	}
}

string s;

int get(int now, string& s){
	for (int idx = 0; idx < s.size(); idx++){
		char c = s[idx];
		if (c == '1'){
			if (lc[now] == 0)
				addlc(now, newint++);
			now = lc[now];
			continue;
		}
		if (c == '2'){
			if (rc[now] == 0)
				addrc(now, newint++);
			now = rc[now];
			continue;
		}
		if (c == 'U'){
			now = par[now];
			continue;
		}
		if (c == 'L'){
			if (l[now] == 0){
				int cnt = 0;
				int tmp = now;
				while (tmp == lc[par[tmp]]){
					cnt ++;
					tmp = par[tmp];
				}
				if (lc[par[tmp]] == 0)
					addlc(par[tmp], newint++);
				tmp = lc[par[tmp]];
				while (cnt --){
					if (rc[tmp] == 0)
						addrc(tmp, newint++);
					tmp = rc[tmp];
				}
			}
			now = l[now];
			continue;
		}
		if (r[now] == 0){
			int cnt = 0;
			int tmp = now;
			while (tmp == rc[par[tmp]]){
				cnt ++;
				tmp = par[tmp];
			}
			if (rc[par[tmp]] == 0)
				addrc(par[tmp], newint++);
			tmp = rc[par[tmp]];
			while (cnt --){
				if (lc[tmp] == 0)
					addlc(tmp, newint++);
				tmp = lc[tmp];
			}
		}
		now = r[now];
	}
	return now;
}

int main(){
	ios_base::sync_with_stdio(false);
	string s, t;
	cin >> s >> t;
	int ds = 0, dt = 0;
	for (auto c : s)
		ds += (c == '1' or c == '2') - (c == 'U');
	for (auto c : t)
		dt += (c == '1' or c == '2') - (c == 'U');
	if (ds < dt){
		swap(ds, dt);
		swap(s, t);
	}
	int v = get(1, s);
	int u = get(1, t);
	int now = 0;
	while (ds > dt){
		now ++;
		v = par[v];
		ds --;
	}
	for (int i = newint-1; i >= 1; i--){
		if (lc[i] == 0)
			addlc(i, newint++);
		if (rc[i] == 0)
			addrc(i, newint++);
	}
	int answer = maxn;
	while (v != u){
		if (r[v] == u or l[v] == u)
			answer = min(answer, now+1);
		if (r[r[v]] == u or l[l[v]] == u)
			answer = min(answer, now+2);
		if (r[r[r[v]]] == u or l[l[l[v]]] == u)
			answer = min(answer, now+3);
		v = par[v];
		u = par[u];
		now += 2;
	}
	answer = min(answer, now);
	cout << answer << endl;

}

Compilation message

board.cpp: In function 'int get(int, std::__cxx11::string&)':
board.cpp:43:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int idx = 0; idx < s.size(); idx++){
                    ~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 768 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 768 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 4 ms 1664 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 5 ms 1792 KB Output is correct
3 Correct 3 ms 1152 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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