Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 奇怪了，为什么老是超时？高手帮看看！带权，用了路径压缩，还是超时

Posted by chunzhenzyd at 2018-04-15 15:49:56 on Problem 1182
```import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int d, x, y;
int result = 0;
Food1182[] foods = new Food1182[n+1];
for(int i=0; i<n+1; i++) {
foods[i] = new Food1182();
}
Food1182 xAncester, yAncester;
Food1182 ancester, enemy, food;
for(int i=0; i<k; i++) {
d = scanner.nextInt();
x = scanner.nextInt();
y = scanner.nextInt();
if(x>n || y>n || (d==2 && x==y)) {
result++;
//				System.out.println((i+1) + "\t" + d + "\t" + x + "\t" + y);
continue;
}
xAncester = foods[x].getAncester();
yAncester = foods[y].getAncester();
if(d == 1) {	// same ancester
if(xAncester == yAncester) {
;
} else if(xAncester.enemy == yAncester || xAncester.food == yAncester) {
result++;
//					System.out.println((i+1) + "\t" + d + "\t" + x + "\t" + y);
} else {	// 不同生态圈，合并
ancester = combine(xAncester, yAncester);
enemy = combine(xAncester.enemy, yAncester.enemy);
food = combine(xAncester.food, yAncester.food);
chain(ancester, enemy, food);
}
} else {	// eat
if(xAncester.food == yAncester) {
;
} else if(xAncester.enemy == yAncester || xAncester == yAncester) {
result++;
//					System.out.println((i+1) + "\t" + d + "\t" + x + "\t" + y);
} else {
ancester = combine(xAncester, yAncester.enemy);
enemy = combine(xAncester.enemy, yAncester.food);
food = combine(xAncester.food, yAncester);
chain(ancester, enemy, food);
}
}
//			draw(i+1, foods, n);
}
System.out.println(result);
scanner.close();
}

public static void chain(Food1182 ancester, Food1182 enemy, Food1182 food) {
ancester.enemy = enemy;
ancester.food = food;
if(enemy != null) {
enemy.enemy = food;
enemy.food = ancester;
}
if(food != null) {
food.enemy = ancester;
food.food = enemy;
}
}

public static Food1182 combine(Food1182 food1, Food1182 food2) {
if(food1 == null) {
return food2;
}
if(food2 == null) {
return food1;
}
if(food1.weight < food2.weight) {
food1.ancester = food2;
food2.weight += food1.weight;
return food2;
} else {
food2.ancester = food1;
food1.weight += food2.weight;
return food1;
}
}
}

class Food1182 {
public int weight;
public Food1182 ancester;
public Food1182 enemy;
public Food1182 food;

public Food1182() {
ancester = this;
enemy = null;
food = null;
}

public Food1182 getAncester() {
Food1182 ancester = this;
while(ancester != ancester.ancester) {
ancester.ancester = ancester.ancester.ancester;
ancester = ancester.ancester;
}
return ancester;
}
}```

Followed by: