Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:奇怪了,为什么老是超时?高手帮看看!带权,用了路径压缩,还是超时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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator