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

Re:奇怪了,为什么老是超时?高手帮看看!带权,用了路径压缩,还是超时

Posted by tredcx at 2018-07-15 20:12:04 on Problem 1182
In Reply To:奇怪了,为什么老是超时?高手帮看看!带权,用了路径压缩,还是超时 Posted by:chunzhenzyd at 2018-04-15 15:49:56
> 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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator