#Practice Codeforces Round #200 div1

A,B,C,D를 해결했다.

 

A. Rational Resistance

GCD처럼 풀면된다.

Code :

#include<stdio.h>

int main() {
	long long int a, b;
	long long int ans = 0;
    scanf("%lld%lld", &a, &b);
	while (a>0&&b>0) {
		long long int c;
		ans += a / b;
		a %= b;
		a ^= b ^= a ^= b;
	}
	printf("%lld", ans);
	return 0;
}

 

B. Alternating Current

결국 ++이나 --는 없다고 생각해도 문제가 동치이기 때문에 스택을 이용해서 해결해주면 된다.

Code :

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;

vector<char>st;

char S[100100];

int main() {
	scanf("%s", S);
	int i;
	int n = strlen(S);
	for (i = 0; i < n; i++) {
		if (st.empty() || st.back() != S[i]) {
			st.push_back(S[i]);
		}
		else {
			st.pop_back();
		}
	}
	if (st.empty())puts("Yes");
	else puts("No");

	return 0;
}

 

C. Read Time

답을 x로 결정해준 후, 각 헤더에 대해서 x만큼씩 이동 할 수 있다고 한다면

왼쪽헤더부터 읽어야 할 곳을 결정해준다.

최대한 많이 읽는게 이득이고, 아래 두가지 중에 한 경우로 결정된다.

1. 왼쪽으로 첫번째 애를 먹으러 갔다가 오른쪽으로 찾아가는 경우

2. 오른쪽으로 갔다가 왼쪽애를 먹는 경우.

두가지를 또 결정해서 문제를 해결해 주면 된다.

나는 2번 방법을 짜는데 또 파라메트릭 서치를 이용했지만, 결국 헤더들이 결정되어있기 때문에 투포인터를 사용해도 된다. 

Code :

#include<stdio.h>
long long int a[212121];
long long int b[212121];
long long int n, m;
long long int gd(long long int a) {
	if (a < 0)return -a;
	return a;
}

bool ff(long long a, long long b, long long c, long long x) {
	if (gd(a - c) + gd(c - b) <= x)return 1;
	return 0;
}
long long int f(long long int x) {
	int i,j;
	int covered = 0;
	for (i = 0; i < n; i++) {
		long long left;
		long long next_covered;
		if (x - (a[i] - b[covered])<0)return 0;
		if (x - gd(a[i] - b[covered]) < 0)continue;
		left = x - gd(b[covered] - a[i]);
		next_covered = covered + 1;
		for (j = covered+1; j < m; j++) {
			if (gd(b[covered] - b[j]) <= left) {
				next_covered = j + 1;
			}
			else
				break;
		}
		int s = next_covered;
		int e = m-1;
		while (s <= e) {
			int mid = (s + e) / 2;
			int k = ff(a[i], b[covered], b[mid], x);
			if (k) {
				s = mid + 1;
				next_covered = mid + 1;
			}
			else {
				e = mid - 1;
			}
		}
		covered = next_covered;
		if (covered == m)return 1;
	}
	return 0;
}

int main() {
	long long int i, j;
	long long int ans;

	scanf("%lld%lld", &n, &m);

	for (i = 0; i < n; i++) {
		scanf("%lld", &a[i]);
	}
	for (i = 0; i < m; i++) {
		scanf("%lld", &b[i]);
	}
	long long s = 0;
	long long e = 20000000000000ll;

	while (s <= e) {
		long long mid = (s + e) / 2;
		long long int k = f(mid);
		if (k) {
			ans = mid;
			e = mid - 1;
		}
		else {
			s = mid + 1;
		}
	}
	printf("%lld", ans);
	return 0;
}

D. Water Tree

 두가지 쿼리가 있는 문제이다.

1. 자신의 자식들을 1으로 바꾼다

2. 자신의 부모들을 0으로 바꾼다.

 

DFS numbering을 한 후, max인덱스트리로 1을 처리하고 , max 세그먼트트리로 2을 처리하면 문제를 해결 할 수 있다. 

#include<stdio.h>
#include<vector>

using namespace std;

vector<int>edge[515151];

int numbering[515151];
int c_s[515151];
int c_e[515151];

int cnt=0;
int tn;
bool is_gone[515151];
void dfs(int w) {
	int i;
	is_gone[w] = 1;
	numbering[w] = cnt;
	c_s[w] = cnt++;
	for (i = 0; i < edge[w].size(); i++) {
		if (is_gone[edge[w][i]])continue;
		dfs(edge[w][i]);
	}
	c_e[w] = cnt - 1;
}

struct xy {
	int x, buf;
};

int min(int a, int b) {
	if (a < b)return a; return b;
}
int max(int a, int b) {
	if (a > b)return a; return b;
}

xy seg_tree[2115151];

void spread(int w) {
	int c1 = w * 2;
	int c2 = w * 2 + 1;
	seg_tree[c1].buf = max(seg_tree[c1].buf, seg_tree[w].buf);
	seg_tree[c1].x = max(seg_tree[c1].buf, seg_tree[c1].x);
	seg_tree[c2].buf = max(seg_tree[c2].buf, seg_tree[w].buf);
	seg_tree[c2].x = max(seg_tree[c2].buf, seg_tree[c2].x);
}

void seg_insert_g(int w, int s, int e, int l, int r, int g) {
	if(l!=r)spread(w);
	if (s == l&&e == r) {
		seg_tree[w].buf = g;
		seg_tree[w].x = max(seg_tree[w].x, g);
		return;
	}
	int mid = (l + r) / 2;
	if (s <= mid) seg_insert_g(w * 2, s, min(e, mid), l, mid, g);
	if (mid + 1 <= e)seg_insert_g(w * 2 + 1, max(s, mid + 1), e, mid + 1, r, g);
}

int seg_search_g(int w, int ww,int l, int r) {
	if(l!=r)spread(w);
	if (l == r&&l == ww)return seg_tree[w].x;
	int mid = (l + r) / 2;
	if (ww <= mid)return seg_search_g(w * 2, ww, l, mid);
	else return seg_search_g(w * 2 + 1, ww, mid + 1, r);
}

int index_tree[2151515];

void ind_insert_g(int w, int g) {
	int i;
	for (i = w + tn; i > 0; i /= 2) {
		index_tree[i] = max(index_tree[i], g);
	}
}

int ind_search_g(int ss, int ee) {
	int s = ss + tn;
	int e = ee + tn;
	int res = 0;
	while (s <= e) {
		if (s % 2 == 1) {
			if (res < index_tree[s])
				res = index_tree[s];
			s++;
		}
		if (e % 2 == 0) {
			if (res < index_tree[e])
				res = index_tree[e];
			e--;
		}
		s /= 2;
		e /= 2;
	}
	return res;
}

int main() {
	int n;
	int i, j;

	scanf("%d", &n);

	for (tn = 1; tn < n; tn *= 2);


	for (i = 0; i < n - 1; i++) {
		int s, e;
		scanf("%d%d", &s, &e);
		edge[s].push_back(e);
		edge[e].push_back(s);
	}

	dfs(1);

	int q;
	scanf("%d", &q);
	for (i = 1; i <= q; i++) {
		int type;
		int who;
		scanf("%d%d", &type, &who);
		if (type == 1) {
			seg_insert_g(1, c_s[who], c_e[who], 0, tn-1, i);
		}
		if (type == 2) {
			ind_insert_g(numbering[who], i);
		}
		if (type == 3) {
			int t1=seg_search_g(1,numbering[who] , 0, tn-1);
			int t2 = ind_search_g(c_s[who], c_e[who]);
			if (t1 > t2)puts("1");
			else puts("0");
		}
	}

	
	return 0;
}