답안 #4746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4746	2013-12-28T05:42:36 Z	tncks0121	특수한 그래프 (IZhO13_specialg)	C++	5 / 100	1000 ms	22688 KB

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>  

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));
					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) it1--;

						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) it2--;

						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() {
	reverse(result.begin(), result.end());
	for(int i = 0; i < result.size(); i++) printf("%d\n", result[i]);
}

int main() {
	int i;

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

	output();

	return 0;
}

Subtask #1

5.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1000 ms	17752 KB	Program timed out
2	Execution timed out	1000 ms	17752 KB	Program timed out
3	Execution timed out	1000 ms	17752 KB	Program timed out
4	Execution timed out	1000 ms	17912 KB	Program timed out
5	Execution timed out	1000 ms	17752 KB	Program timed out
6	Execution timed out	1000 ms	17752 KB	Program timed out
7	Execution timed out	1000 ms	17752 KB	Program timed out
8	Execution timed out	1000 ms	17752 KB	Program timed out
9	Execution timed out	1000 ms	17924 KB	Program timed out
10	Execution timed out	1000 ms	17932 KB	Program timed out
11	Correct	76 ms	22688 KB	Output is correct
12	Execution timed out	1000 ms	19536 KB	Program timed out
13	Execution timed out	1000 ms	20224 KB	Program timed out
14	Execution timed out	1000 ms	19344 KB	Program timed out
15	Execution timed out	1000 ms	19692 KB	Program timed out
16	Execution timed out	1000 ms	19544 KB	Program timed out
17	Execution timed out	1000 ms	20924 KB	Program timed out
18	Execution timed out	1000 ms	20924 KB	Program timed out
19	Execution timed out	1000 ms	20924 KB	Program timed out
20	Execution timed out	1000 ms	22176 KB	Program timed out