12058 - Highway Monitor

All about problems in Volume 120. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

12058 - Highway Monitor

Post by sith » Mon Jun 25, 2012 6:13 pm

Hello!
I've got WA for this problem.
Here is my solution. What is wrong?

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.StringTokenizer;

class Main {


    public static void main(String[] args) {

       BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));


        String line;
        try {
            while ((line = reader.readLine()) != null) {
                int caseCount = Integer.parseInt(line.trim());

                for (int i = 1; i <= caseCount; i++) {

                    StringBuilder builder = new StringBuilder();
                    builder.append("Case #").append(i).append(": ");
                    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
                    int n = Integer.parseInt(tokenizer.nextToken());
                    int h = Integer.parseInt(tokenizer.nextToken());
                    int k = Integer.parseInt(tokenizer.nextToken());

                    Map<Integer, Set<Route>> cities = new HashMap<Integer, Set<Route>>();

                    for (int j = 0; j < h; j++) {
                        tokenizer = new StringTokenizer(reader.readLine());
                        int x = Integer.parseInt(tokenizer.nextToken());
                        int y = Integer.parseInt(tokenizer.nextToken());
                        Route route = new Route(x, y);
                        addRoute(cities, x, route);
                        addRoute(cities, y, route);
                    }

                    PriorityQueue<Routes> routes = new PriorityQueue<Routes>();
                    for (Map.Entry<Integer, Set<Route>> integerSetEntry : cities.entrySet()) {
                        routes.add(new Routes(integerSetEntry.getKey(), integerSetEntry.getValue()));
                    }

                    Set<Integer> result = new HashSet<Integer>();
                    Set<Route> coveredRoutes = new HashSet<Route>();
                    Routes poll;
                    while ((poll = routes.poll()) != null) {

                        if (coveredRoutes.containsAll(poll.routes)) {
                            continue;
                        }
                        else {
                            coveredRoutes.addAll(poll.routes);
                            result.add(poll.city);
                        }

                        if (coveredRoutes.size() == h) {
                            break;
                        }

                        if (result.size() > k) {
                            break;
                        }
                    }

                    if (result.size() > k) {
                        System.out.println(builder.append("no").toString());
                        continue;
                    }
                    else {
                        builder.append("yes");
                        for (Integer city : result) {
                            builder.append(" ").append(city);
                        }
                        System.out.println(builder);

                    }
                }
            }
        }
        catch (IOException e) {
        }
    }

    private static void addRoute(final Map<Integer, Set<Route>> cities, final int city, final Route route) {
        Set<Route> routes = cities.get(city);

        if (routes == null) {
            routes = new HashSet<Route>();
            cities.put(city, routes);
        }
        routes.add(route);
    }

    static class Routes implements Comparable<Routes> {
        int city;
        Set<Route> routes;

        public int compareTo(final Routes o) {
            return o.routes.size() - routes.size();
        }

        Routes(final int city, final Set<Route> routes) {
            this.city = city;
            this.routes = routes;
        }
    }


    static class Route {
        final int x;
        final int y;

        Route(final int x, final int y) {
            this.x = Math.min(x, y);
            this.y = Math.max(x, y);
        }

        @Override
        public boolean equals(final Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            final Route route = (Route) o;
            if (x != route.x) {
                return false;
            }
            if (y != route.y) {
                return false;
            }
            return true;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }
}

Post Reply

Return to “Volume 120 (12000-12099)”