답안 #4748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4748 2013-12-28T08:45:27 Z tncks0121 특수한 그래프 (IZhO13_specialg) C++
100 / 100
100 ms 22692 KB
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

struct DisjointSet {
	vector<int> parent, rnk;
	DisjointSet(): parent(), rnk() { }

	void resize(uint size) { 
		parent.resize(size+1);
		rnk.resize(size+1, 1);
		for(uint i = 1; i <= size; i++) parent[i] = i;
	}

	int group (int u) {
		int ret = u;
		while(ret != parent[ret]) ret = parent[ret];
		while(u != ret) {
			int p = parent[u];
			parent[u] = ret;
			u = p;
		}
		return ret;
	}

	bool merge (int u, int v) {
		int a = group(u);
		int b = group(v);
		if(a == b) return false;
		if(rnk[a] > rnk[b]) swap(a, b);
		else if(rnk[a] == rnk[b]) ++rnk[b];
		parent[a] = b;
		return true;
	}
};

const int lgN_ = 17, N_ = 100005;
const int Q_ = 100005;

int N; // 노드 수
int Next[lgN_][N_]; // Next[k, i]: i에서 2^k만큼 갔을 때 노드 번호
vector<int> Rev[N_]; // reverse graph

int Level[N_], Root[N_];

int Q;
pii Query[Q_];
bool deleted[N_];

int CYCN;
int cycle[N_], cycle_wh[N_], cycle_length[N_];
set<pii> cycle_group[N_];

DisjointSet component;

vector<int> result;

void input() {
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d", &Next[0][i]);
	scanf("%d", &Q);
	for(int i = 1; i <= Q; i++) {
		int q; scanf("%d", &q);
		if(q == 1) scanf("%d", &Query[i].first), Query[i].second = -1, deleted[Query[i].first] = true;
		else scanf("%d%d", &Query[i].first, &Query[i].second);
	}
}

void fillNext() {
	for(int k = 1; k < lgN_; k++)
		for(int i = 1; i <= N; i++) {
			int x = Next[k - 1][i];
			if(x == 0) continue;
			Next[k][i] = Next[k - 1][x];
		}
}

int go (int u, int len) {
	for(int k = 0; k < lgN_; k++) {
		if(u > 0 && (len & (1<<k))) u = Next[k][u];
	}
	return u;
}

void mergeComponent() {
	component.resize(N);
	for(int u = 1; u <= N; u++) {
		int v = Next[0][u];
		if(v > 0 && !deleted[u]) component.merge(u, v);
	}
}

void findCycle() {
	mergeComponent();

	vector<int> pth;
	vector<bool> visited(N+1);
	for(int s = 1; s <= N; s++) if(!cycle[s]) {
		pth.clear();
		int last = -1;
		for(int u = s; !visited[u] && u > 0; ) {
			pth.push_back(u);
			visited[u] = true;
			u = Next[0][u];
			last = u;
		}
		if(last > 0) {
			int found_x = -1;
			for(int i = 0; i < pth.size(); i++) {
				if(pth[i] == last) found_x = i, ++CYCN;
				if(found_x >= 0) cycle[pth[i]] = CYCN, cycle_wh[pth[i]] = i - found_x, 
					++cycle_length[CYCN];
			}
			if(CYCN == 3) {
				N = N;
			}
			int last = -1, first = -1;
			int delnd = -1;
			for(int i = found_x; i < pth.size(); i++) {
				int u = pth[i];
				int v = Next[0][u];
				if(deleted[u]) delnd = i - found_x;

				if(component.group(u) != component.group(v)) {
					if(i+1 == pth.size() && first >= 0) cycle_group[CYCN].insert(pii(0, first));
					if(last >= 0) cycle_group[CYCN].insert(pii(last+1, i-found_x));
					else first = i-found_x;
					last = i-found_x;
				}else {
					if(i+1 == pth.size()) {
						if(first >= 0) {
							if(first < last+1) first += cycle_length[CYCN];
							cycle_group[CYCN].insert(pii(last+1, first));
						}else if(delnd >= 0) { // 모두 선 하나로 연결되어 있음
							int s = (delnd + 1) % cycle_length[CYCN];
							cycle_group[CYCN].insert(pii(s, s + cycle_length[CYCN] - 1));
						}
					}
				}
			}
		}
	}
}

void fillLevel() {
	for(int u = 1; u <= N; u++) 
		if(Next[0][u] > 0) Rev[Next[0][u]].push_back(u);

	queue<int> que;
	for(int s = 1; s <= N; s++) if(cycle[s] || Next[0][s] == 0) {
		while(!que.empty()) que.pop();
		que.push(s); que.push(-1); Root[s] = s;
		while(!que.empty()) {
			int u = que.front(); que.pop();
			int p = que.front(); que.pop();
			for(int e = 0; e < Rev[u].size(); e++) {
				int v = Rev[u][e];
				if(v != p && !cycle[v]) {
					Level[v] = Level[u] + 1;
					Root[v] = s;
					que.push(v); que.push(u);
				}
			}
		}
	}
}

void solveQuery() {
	for(int q = Q; q > 0; q--) {
		if(q == 2771) {
			q = q;
		}
		int u = Query[q].first, v = Query[q].second;
		if(v == -1) {
			v = Next[0][u];
			component.merge(u, v);
			int c = cycle[u];
			deleted[u] = 0;

			if(c > 0) {
				set<pii>& gr = cycle_group[c];
				if(gr.size() <= 1) {
					gr.clear();
				}else {
					set<pii>::iterator itv = gr.lower_bound( pii(cycle_wh[v], cycle_wh[v]) );
					set<pii>::iterator itu = itv; 
					if(itu == gr.begin()) itu = gr.end();
					--itu;

					int ua = itu->first, ub = itu->second;
					int va = itv->first, vb = itv->second;

					gr.erase(itu);
					gr.erase(itv);
					if(vb < ua) vb += cycle_length[c];
					gr.insert( pii(ua, vb) );
				}
			}
		}else {
			int ret = 0, a = u, b = v;
			if(component.group(u) == component.group(v)) {
				bool is_u_cycle = (cycle[u] > 0);
				bool is_v_cycle = (cycle[v] > 0);

				if(q == 2771) fprintf(stderr, "%d %d\n", is_u_cycle, is_v_cycle);

				if(!is_u_cycle && !is_v_cycle) {
					int len = Level[u] - Level[v];
					if(len >= 0 && go(u, len) == v) ret = len;
				}else if(!is_u_cycle && is_v_cycle) {
					int len = Level[u] - Level[Root[u]];
					if(len >= 0 && go(u, len) == Root[u]) ret = len;
					u = Root[u]; is_u_cycle = true;
				}

				if(is_u_cycle && is_v_cycle) {
					if(cycle_group[cycle[u]].empty()) {
						int len = cycle_wh[v] - cycle_wh[u];
						if(len < 0) len += cycle_length[cycle[u]];
						ret += len;
					}else {
						int uw1 = cycle_wh[u], uw2 = uw1 + cycle_length[cycle[u]];
						set<pii>& gr = cycle_group[cycle[u]];

						set<pii>::iterator it1 = gr.lower_bound ( pii(uw1, uw1) );
						if(it1 == gr.end()) it1--;
						while(it1 != gr.end() && !(it1->first <= uw1 && uw1 <= it1->second) && it1->second >= uw1) if(it1 == gr.begin()) it1 = gr.end(); else it1--;
						if(it1 != gr.end() && !(it1->first <= uw1 && uw1 <= it1->second)) it1 = gr.end();

						set<pii>::iterator it2 = gr.lower_bound ( pii(uw2, uw2) );
						if(it2 == gr.end()) it2--;
						while(it2 != gr.end() && !(it2->first <= uw2 && uw2 <= it2->second) && it2->second >= uw2) if(it2 == gr.begin()) it2 = gr.end(); else it2--;
						if(it2 != gr.end() && !(it2->first <= uw2 && uw2 <= it2->second)) it2 = gr.end();

						set<pii>::iterator it = (it1 != gr.end()) ? it1 : it2;
						if(it == gr.end()) ret = -1;
						else {
							int uw = (it1 != gr.end()) ? uw1 : uw2;
							if(it->first <= cycle_wh[v] && cycle_wh[v] <= it->second) {
								if(cycle_wh[v] >= uw) ret += cycle_wh[v] - uw;
								else ret = -1;
							}else if(it->first <= cycle_wh[v] + cycle_length[cycle[u]] && cycle_wh[v] + cycle_length[cycle[u]] <= it->second) {
								if(cycle_wh[v] + cycle_length[cycle[u]] >= uw) ret += cycle_wh[v] + cycle_length[cycle[u]] - uw;
								else ret = -1;
							}else {
								ret = -1;
							}
						}
					}
				}
			}
			if(a == b) ret = 0;
			else if(ret == 0) ret = -1;
			result.push_back(ret);
		}
	}
}

void output() {
	for(int i = (int)result.size() - 1; i >= 0; i--) printf("%d\n", result[i]);
}

int main() {
	int i;

	input();
	
	fillNext();
	findCycle();
	fillLevel();
	
	solveQuery();

	output();

	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 17756 KB Output is correct
2 Correct 4 ms 17756 KB Output is correct
3 Correct 0 ms 17756 KB Output is correct
4 Correct 4 ms 17916 KB Output is correct
5 Correct 0 ms 17756 KB Output is correct
6 Correct 16 ms 17920 KB Output is correct
7 Correct 8 ms 17924 KB Output is correct
8 Correct 16 ms 17932 KB Output is correct
9 Correct 8 ms 17928 KB Output is correct
10 Correct 8 ms 17936 KB Output is correct
11 Correct 80 ms 22688 KB Output is correct
12 Correct 72 ms 20400 KB Output is correct
13 Correct 76 ms 21316 KB Output is correct
14 Correct 68 ms 20152 KB Output is correct
15 Correct 76 ms 20508 KB Output is correct
16 Correct 80 ms 20440 KB Output is correct
17 Correct 84 ms 22008 KB Output is correct
18 Correct 88 ms 22004 KB Output is correct
19 Correct 100 ms 22004 KB Output is correct
20 Correct 76 ms 22692 KB Output is correct