답안 #4744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4744	2013-12-28T04:56:06 Z	tncks0121	특수한 그래프 (IZhO13_specialg)	C++	5 / 100	1000 ms	23076 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_ = 18, 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 {
			if(result.size() == 1500) {
				N = N;
			}

			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	18140 KB	Program timed out
2	Execution timed out	1000 ms	18140 KB	Program timed out
3	Execution timed out	1000 ms	18140 KB	Program timed out
4	Execution timed out	1000 ms	18300 KB	Program timed out
5	Execution timed out	1000 ms	18140 KB	Program timed out
6	Execution timed out	1000 ms	18140 KB	Program timed out
7	Execution timed out	1000 ms	18140 KB	Program timed out
8	Execution timed out	1000 ms	18140 KB	Program timed out
9	Execution timed out	1000 ms	18312 KB	Program timed out
10	Execution timed out	1000 ms	18320 KB	Program timed out
11	Correct	72 ms	23076 KB	Output is correct
12	Execution timed out	1000 ms	19924 KB	Program timed out
13	Execution timed out	1000 ms	20612 KB	Program timed out
14	Execution timed out	1000 ms	19732 KB	Program timed out
15	Execution timed out	1000 ms	20080 KB	Program timed out
16	Execution timed out	1000 ms	19932 KB	Program timed out
17	Execution timed out	1000 ms	21312 KB	Program timed out
18	Execution timed out	1000 ms	21312 KB	Program timed out
19	Execution timed out	1000 ms	21312 KB	Program timed out
20	Execution timed out	1000 ms	22564 KB	Program timed out