oj.uz

답안 #17564

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
17564 2015-12-28T05:38:01 Z gs14004 특수한 그래프 (IZhO13_specialg) C++14
0 / 100
 1000 ms 18908 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int,int> pi;

struct disj{
	int pa[100005];
	void init(int n){
		for(int i=0; i<=n; i++) pa[i] = i;
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p), q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;

struct query{
	int t, a, b;
}q[100005];

int n, m, a[100005], kill[100005];
vector<int> graph[100005], rev[100005];

int indeg[100005];
int cyclab[100005], cycidx[100005], cycsz[100005], cycp; 
int treein[100005], treeout[100005], root[100005], dep[100005], treep; 

void dfs(int x, int r){
	treein[x] = ++treep;
	root[x] = r;
	for(auto &i : rev[x]){
		if(cyclab[i]) continue;
		dep[i] = dep[x] + 1;
		dfs(i, r);
	}
	treeout[x] = ++treep;
}

void proc_tree(){
	for(int i=1; i<=n; i++){
		if(rev[i].size() != indeg[i]){
			dfs(i, i);
		}
	}
}

queue<int> que;

void proc_cycle(){
	for(int i=1; i<=n; i++){
		if(indeg[i] == 0) que.push(i);
	}
	while(!que.empty()){
		int x = que.front();
		que.pop();
		for(auto &i : graph[x]){
			indeg[i]--;
			if(indeg[i] == 0) que.push(i);
		}
	}
	for(int i=1; i<=n; i++){
		if(indeg[i] && !cyclab[i]){
			int p = i;
			cycp++;
			while(!cyclab[p]){
				cyclab[p] = cycp;
				cycidx[p] = ++cycsz[cycp];
				p = a[p];
			}
		}
	}
}

inline bool inside(int a, int b){
	return treein[a] <= treein[b] && treeout[b] <= treeout[a];
}

int solve(int p, int q){
	if(cyclab[p] && cyclab[q]){
		int dx = cycidx[q] - cycidx[p] + cycsz[cyclab[p]];
		dx %= cycsz[cyclab[p]];
		return dx;
	}
	if(cyclab[p] && !cyclab[q]){
		return -1;
	}
	if(!cyclab[p] && cyclab[q]){
		return dep[p] + solve(root[p], q);
	}
	if(inside(q, p)){
		return dep[p] - dep[q];
	}
	return -1;
}

int main(){
	cin >> n;
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
		kill[a[i]] = (a[i] == 0);
		if(a[i]){
			rev[a[i]].push_back(i);
			graph[i].push_back(a[i]);
			indeg[a[i]]++;
		}
	}
	cin >> m;
	for(int i=0; i<m; i++){
		scanf("%d",&q[i].t);
		if(q[i].t == 1){
			scanf("%d",&q[i].a);
			kill[q[i].a] = 1;
		}
		else{
			scanf("%d %d",&q[i].a, &q[i].b);
		}
	}
	reverse(q, q+m);
	proc_cycle();
	proc_tree();
	disj.init(n);
	for(int i=1; i<=n; i++){
		if(!kill[i]) disj.uni(i, a[i]);
	}
	vector<int> stk;
	for(int i=0; i<m; i++){
		if(q[i].t == 1){
			disj.uni(q[i].a, a[q[i].a]);
		}
		else{
			if(disj.find(q[i].a) != disj.find(q[i].b)) stk.push_back(-1);
			else stk.push_back(solve(q[i].a, q[i].b));
		}
	}
	while(!stk.empty()){
		printf("%d\n",stk.back());
		stk.pop_back();
	}
}

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 11880 KB Program timed out
2 Execution timed out 1000 ms 11880 KB Program timed out
3 Execution timed out 1000 ms 11880 KB Program timed out
4 Execution timed out 1000 ms 11880 KB Program timed out
5 Execution timed out 1000 ms 11880 KB Program timed out
6 Execution timed out 1000 ms 11880 KB Program timed out
7 Execution timed out 1000 ms 11880 KB Program timed out
8 Execution timed out 1000 ms 11880 KB Program timed out
9 Execution timed out 1000 ms 11880 KB Program timed out
10 Execution timed out 1000 ms 11880 KB Program timed out
11 Incorrect 50 ms 18908 KB Output isn't correct
12 Execution timed out 1000 ms 15604 KB Program timed out
13 Execution timed out 1000 ms 17032 KB Program timed out
14 Execution timed out 1000 ms 15120 KB Program timed out
15 Execution timed out 1000 ms 15904 KB Program timed out
16 Execution timed out 1000 ms 15752 KB Program timed out
17 Execution timed out 1000 ms 18472 KB Program timed out
18 Execution timed out 1000 ms 18472 KB Program timed out
19 Execution timed out 1000 ms 18476 KB Program timed out
20 Incorrect 80 ms 18908 KB Output isn't correct