oj.uz

답안 #17566

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
17566 2015-12-28T05:47:37 Z gs14004 특수한 그래프 (IZhO13_specialg) C++14
0 / 100
 97 ms 19336 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(a[i] == 0 || cyclab[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();
		if(!a[x]) continue;
		indeg[a[x]]--;
		if(indeg[a[x]] == 0) que.push(a[x]);
	}
	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[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 Incorrect 2 ms 11888 KB Output isn't correct
2 Incorrect 4 ms 12024 KB Output isn't correct
3 Incorrect 3 ms 11888 KB Output isn't correct
4 Incorrect 0 ms 12072 KB Output isn't correct
5 Incorrect 3 ms 11888 KB Output isn't correct
6 Incorrect 14 ms 12152 KB Output isn't correct
7 Incorrect 9 ms 12160 KB Output isn't correct
8 Incorrect 11 ms 12172 KB Output isn't correct
9 Incorrect 9 ms 12160 KB Output isn't correct
10 Incorrect 14 ms 12176 KB Output isn't correct
11 Incorrect 80 ms 18912 KB Output isn't correct
12 Incorrect 81 ms 16476 KB Output isn't correct
13 Incorrect 68 ms 17884 KB Output isn't correct
14 Incorrect 73 ms 15944 KB Output isn't correct
15 Incorrect 70 ms 16688 KB Output isn't correct
16 Incorrect 68 ms 16560 KB Output isn't correct
17 Incorrect 95 ms 19332 KB Output isn't correct
18 Incorrect 84 ms 19332 KB Output isn't correct
19 Incorrect 97 ms 19336 KB Output isn't correct
20 Incorrect 52 ms 18912 KB Output isn't correct