oj.uz

답안 #17565

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
17565 2015-12-28T05:41:43 Z gs14004 특수한 그래프 (IZhO13_specialg) C++14
0 / 100
 99 ms 19332 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();
		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 Incorrect 0 ms 11884 KB Output isn't correct
2 Incorrect 0 ms 12020 KB Output isn't correct
3 Incorrect 4 ms 11884 KB Output isn't correct
4 Incorrect 5 ms 12068 KB Output isn't correct
5 Incorrect 2 ms 11884 KB Output isn't correct
6 Incorrect 11 ms 12148 KB Output isn't correct
7 Incorrect 13 ms 12156 KB Output isn't correct
8 Incorrect 13 ms 12168 KB Output isn't correct
9 Incorrect 0 ms 12156 KB Output isn't correct
10 Incorrect 0 ms 12172 KB Output isn't correct
11 Incorrect 69 ms 18908 KB Output isn't correct
12 Incorrect 73 ms 16480 KB Output isn't correct
13 Incorrect 85 ms 17880 KB Output isn't correct
14 Incorrect 69 ms 15940 KB Output isn't correct
15 Incorrect 59 ms 16676 KB Output isn't correct
16 Incorrect 52 ms 16556 KB Output isn't correct
17 Incorrect 99 ms 19332 KB Output isn't correct
18 Incorrect 98 ms 19328 KB Output isn't correct
19 Incorrect 92 ms 19332 KB Output isn't correct
20 Incorrect 68 ms 18908 KB Output isn't correct