| ||||||||||
| 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