답안 #4745

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4745	2013-12-28T05:37:11 Z	tncks0121	특수한 그래프 (IZhO13_specialg)	C++	5 / 100	1000 ms	39972 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_ = 200005;
const int Q_ = 200005;

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	35036 KB	Program timed out
2	Execution timed out	1000 ms	35036 KB	Program timed out
3	Execution timed out	1000 ms	35036 KB	Program timed out
4	Execution timed out	1000 ms	35196 KB	Program timed out
5	Execution timed out	1000 ms	35036 KB	Program timed out
6	Execution timed out	1000 ms	35036 KB	Program timed out
7	Execution timed out	1000 ms	35036 KB	Program timed out
8	Execution timed out	1000 ms	35036 KB	Program timed out
9	Execution timed out	1000 ms	35208 KB	Program timed out
10	Execution timed out	1000 ms	35216 KB	Program timed out
11	Correct	68 ms	39972 KB	Output is correct
12	Execution timed out	1000 ms	36820 KB	Program timed out
13	Execution timed out	1000 ms	37508 KB	Program timed out
14	Execution timed out	1000 ms	36628 KB	Program timed out
15	Execution timed out	1000 ms	36976 KB	Program timed out
16	Execution timed out	1000 ms	36828 KB	Program timed out
17	Execution timed out	1000 ms	38208 KB	Program timed out
18	Execution timed out	1000 ms	38208 KB	Program timed out
19	Execution timed out	1000 ms	38208 KB	Program timed out
20	Execution timed out	1000 ms	39460 KB	Program timed out