Submission #4751

#	Time	Username	Problem	Language	Result	Execution time	Memory
4751		tncks0121	Special graph (IZhO13_specialg)	C++98	100 / 100	92 ms	22692 KiB

specialg

#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];
			}
			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--) {
		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(!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;
}

• Subtask 1: 100 / 100