Формат ввода

Формат вывода

Пример 1

Пример 2

Пример 3

Примечания

public class CablesSolution {

    private static final long MODULLO = 2147483647L;

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);

        int n = in.readInt();
        int k = in.readInt();
        int m = in.readInt();

        DisjointUnionSets dsu = new DisjointUnionSets(n + 1);

        for (int i = 0; i < k; i++) {
            int u = in.readInt();
            int v = in.readInt();

            dsu.union(u, v);
        }

        Edge[] edges = new Edge[m]; // (4 + 4 + 8) * 2M = 32M

        for (int i = 0; i < m; i++) {
            int u = in.readInt();
            int v = in.readInt();
            long p = in.readLong();
            edges[i] = new Edge(u, v, p);
        }

        Arrays.sort(edges);

        long res = 1;
        boolean addedEdge = false;

        for (Edge edge : edges) {
            if (!dsu.check(edge.getU(), edge.getV())) {
                dsu.union(edge.getU(), edge.getV());
                res = (res * edge.getP()) % MODULLO;
                addedEdge = true;
            }
        }

        if (!dsu.isJoint()) {
            res = -1;
        } else if (!addedEdge) {
            res = 0;
        }

        pw.println(res);
        pw.flush();
        pw.close();
    }

    public static class DisjointUnionSets {

        private int[] rank; // 4M
        private int[] parent; // 4M

        DisjointUnionSets(int size) {
            rank = new int[size];
            parent = new int[size];

            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }

        int find(int target) {
            if (parent[target] != target) {
                parent[target] = find(parent[target]);
            }

            return parent[target];
        }

        boolean check(int x, int y) {
            return find(x) == find(y);
        }

        void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);

            if (xRoot == yRoot) {
                return;
            }

            if (rank[xRoot] < rank[yRoot]) {
                parent[xRoot] = yRoot;
            } else if (rank[yRoot] < rank[xRoot]) {
                parent[yRoot] = xRoot;
            } else {
                parent[yRoot] = xRoot;
                rank[xRoot] = rank[xRoot] + 1;
            }
        }

        boolean isJoint() {
            int parent = -1;

            for (int i = 1; i < rank.length; i++) {
                if (parent == -1) {
                    parent = find(i);
                } else {
                    if (parent != find(i)) {
                        return false;
                    }
                }
            }

            return true;
        }
    }

    private static class Edge implements Comparable<Edge> {

        private int u;
        private int v;
        private long p;

        Edge(int u, int v, long p) {
            this.u = u;
            this.v = v;
            this.p = p;
        }

        int getU() {
            return u;
        }

        int getV() {
            return v;
        }

        long getP() {
            return p;
        }

        @Override
        public int compareTo(Edge edge) {
            return Long.compare(p, edge.p);
        }
    }
}

Формат ввода

Формат вывода

Пример

Примечания

import copy
import math
import time
import tkinter
from enum import Enum

FRAMES_PER_SECOND = 60
TIME_BETWEEN_FRAMES = int(1000 / FRAMES_PER_SECOND)


class Rectangle(object):

    def __init__(self, left_x, left_y, width, height, color, angle=0.0):
        self.center_x = left_x + width / 2
        self.center_y = left_y + height / 2
        self.width = width
        self.height = height
        self.color = color
        self.angle = angle

    def get_left_x(self):
        return self.center_x - self.width / 2

    def set_left_x(self, left_x):
        self.center_x = left_x + self.width / 2

    def get_left_y(self):
        return self.center_y - self.height / 2

    def set_left_y(self, left_y):
        self.center_y = left_y + self.height / 2

    left_x = property(get_left_x, set_left_x)
    left_y = property(get_left_y, set_left_y)


class Circle(object):

    def __init__(self, left_x, left_y, radius, color):
        self.center_x = left_x + radius
        self.center_y = left_y + radius
        self.radius = radius
        self.color = color
        self.angle = 0

    def get_left_x(self):
        return self.center_x - self.radius

    def set_left_x(self, left_x):
        self.center_x = left_x + self.radius

    def get_left_y(self):
        return self.center_y - self.radius

    def set_left_y(self, left_y):
        self.center_y = left_y + self.radius

    left_x = property(get_left_x, set_left_x)
    left_y = property(get_left_y, set_left_y)


class AnimationType(Enum):
    MOVE = 1
    ROTATE = 2
    SCALE = 3


class Animation(object):

    def __init__(self, time, cycle):
        self.time = time
        self.cycle = cycle

    def scale(self, time_spent):
        return 1

    def move(self, time_spent):
        return 0, 0

    def angle(self, time_spent):
        return 0

    def _cycle_progress(self, time_spent):
        if self.cycle:
            cycle_time = time_spent % (self.time * 2)
            if cycle_time > self.time:
                return 1 - (cycle_time - self.time) / self.time
            else:
                return cycle_time / self.time
        else:
            if time_spent < self.time:
                cycle_time = time_spent % self.time
                return cycle_time / self.time
            else:
                return 1


class MoveAnimation(Animation):

    def __init__(self, figure, to_x, to_y, time, cycle):
        super().__init__(time, cycle)
        self.from_x = figure.center_x
        self.from_y = figure.center_y
        self.to_x = to_x
        self.to_y = to_y

    def move(self, time_spent):
        cycle_progress = super()._cycle_progress(time_spent)
        diff_x = self.to_x - self.from_x
        diff_y = self.to_y - self.from_y
        return diff_x * cycle_progress, diff_y * cycle_progress


class ScaleAnimation(Animation):

    def __init__(self, destination_scale, time, cycle):
        super().__init__(time, cycle)
        self.destination_scale = destination_scale

    def scale(self, time_spent):
        cycle_progress = super()._cycle_progress(time_spent)
        return 1 + (self.destination_scale - 1) * cycle_progress


class RotateAnimation(Animation):

    def __init__(self, rotate_angle, time, cycle):
        super().__init__(time, cycle)
        self.rotate_angle = rotate_angle

    def angle(self, time_spent):
        cycle_progress = super()._cycle_progress(time_spent)
        return self.rotate_angle * cycle_progress


class Transformer(object):

    def scale(self, scale):
        pass

    def move(self, diff_x, diff_y):
        pass

    def rotate(self, angle):
        pass


class RectangleTransformer(Transformer):

    def __init__(self, rectangle):
        self.rectangle = rectangle

    def scale(self, scale):
        self.rectangle.width = self.rectangle.width * scale
        self.rectangle.height = self.rectangle.height * scale

    def move(self, diff_x, diff_y):
        self.rectangle.center_x = self.rectangle.center_x + diff_x
        self.rectangle.center_y = self.rectangle.center_y + diff_y

    def rotate(self, angle):
        self.rectangle.angle = (self.rectangle.angle + angle) % 360


class CircleTransformer(Transformer):

    def __init__(self, circle):
        self.circle = circle

    def scale(self, scale):
        self.circle.radius = self.circle.radius * scale

    def move(self, diff_x, diff_y):
        self.circle.center_x = self.circle.center_x + diff_x
        self.circle.center_y = self.circle.center_y + diff_y

    def rotate(self, angle):
        pass


class Drawer(object):

    def draw(self, canvas, spent_time):
        pass


class AnimationApplier(object):

    @staticmethod
    def apply_animations(spent_time, transformer, animations):
        for animation in animations:
            transformer.scale(animation.scale(spent_time))
            diff_x, diff_y = animation.move(spent_time)
            transformer.move(diff_x, diff_y)
            transformer.rotate(animation.angle(spent_time))


class RectangleDrawer(Drawer):

    def __init__(self, rectangle, animations):
        self.rectangle = rectangle
        self.animations = animations

    def draw(self, canvas, spent_time):
        rect = self._transform_rect_with_animations(spent_time)
        rect_points = self._get_rectangle_points(rect)
        rotated_points = self._rotate(rect_points, rect.angle, [rect.center_x, rect.center_y])
        canvas.create_polygon(rotated_points, fill=rect.color)

    def _transform_rect_with_animations(self, spent_time):
        rect = copy.copy(self.rectangle)
        transformer = RectangleTransformer(rect)
        AnimationApplier.apply_animations(spent_time, transformer, self.animations)

        return transformer.rectangle

    @staticmethod
    def _get_rectangle_points(rect):
        half_width = rect.width / 2
        half_height = rect.height / 2
        return [
            [rect.center_x - half_width, rect.center_y - half_height],
            [rect.center_x - half_width, rect.center_y + half_height],
            [rect.center_x + half_width, rect.center_y + half_height],
            [rect.center_x + half_width, rect.center_y - half_height]
        ]

    @staticmethod
    def _rotate(points, angle, center):
        angle = math.radians(angle)
        cos_val = math.cos(angle)
        sin_val = math.sin(angle)
        cx, cy = center
        new_points = []
        for x_old, y_old in points:
            x_old -= cx
            y_old -= cy
            x_new = x_old * cos_val - y_old * sin_val
            y_new = x_old * sin_val + y_old * cos_val
            new_points.append([x_new + cx, y_new + cy])

        return new_points


class CircleDrawer(Drawer):

    def __init__(self, circle, animations):
        self.circle = circle
        self.animations = animations

    def draw(self, canvas, spent_time):
        circle = self._transform_rect_with_animations(spent_time)
        size = circle.radius * 2
        canvas.create_oval(circle.left_x, circle.left_y, circle.left_x + size, circle.left_y + size, fill=circle.color)

    def _transform_rect_with_animations(self, spent_time):
        circle = copy.copy(self.circle)
        transformer = CircleTransformer(circle)
        AnimationApplier.apply_animations(spent_time, transformer, self.animations)

        return transformer.circle


class Scene(object):

    def __init__(self, canvas, animated_symbols):
        self.canvas = canvas
        self.drawers = self._get_generated_drawers(animated_symbols)

    @staticmethod
    def _get_generated_drawers(animated_symbols):
        drawers = []
        for animated_symbol in animated_symbols:
            figure = animated_symbol.figure
            animations = animated_symbol.animations
            if isinstance(figure, Rectangle):
                drawer = RectangleDrawer(figure, animations)
            elif isinstance(figure, Circle):
                drawer = CircleDrawer(figure, animations)
            else:
                raise Exception()

            drawers.append(drawer)

        return drawers

    def draw(self, time_spent):
        self.canvas.delete("all")
        for drawer in self.drawers:
            drawer.draw(self.canvas, time_spent)

        self.canvas.pack()


class Timer(object):
    def __init__(self):
        self.started_time = None

    def start(self):
        self.started_time = self._current_time()

    def time_spent(self):
        current_time = self._current_time()
        return current_time - self.started_time

    @staticmethod
    def _current_time():
        return int(round(time.time() * 1000))


def scene_loop(window, scene, timer):
    time_spent = timer.time_spent()
    scene.draw(time_spent)
    window.after(TIME_BETWEEN_FRAMES, scene_loop, window, scene, timer)


def configure_window_location(window, canvas_width, canvas_height):
    screen_width = window.winfo_screenwidth()
    screen_height = window.winfo_screenheight()

    x = (screen_width / 2) - (canvas_width / 2)
    y = (screen_height / 2) - (canvas_height / 2)
    window.geometry('%dx%d+%d+%d' % (canvas_width, canvas_height, x, y))


class AnimatedSymbol(object):

    def __init__(self, figure, animations):
        self.figure = figure
        self.animations = animations


class AnimationsParser(object):

    def parse_animated_symbols(self, file_path):
        with open(file_path) as f:
            lines = f.readlines()

        canvas_width, canvas_height = self._parse_size(lines[0])
        symbols_count = int(lines[1])

        animated_symbols = []
        current = 2
        for i in range(symbols_count):
            figure = self._parse_figure(lines[current])
            current += 1

            symbol_animations = self._parse_animations(figure, current, lines)
            current += 1 + len(symbol_animations)

            animated_symbol = AnimatedSymbol(figure, symbol_animations)
            animated_symbols.append(animated_symbol)

        return canvas_width, canvas_height, animated_symbols

    def _parse_size(self, line):
        parts = line.split(" ")
        return int(parts[0]), int(parts[1])

    def _parse_animations(self, figure, current, lines):
        animations = []
        animations_count = int(lines[current])
        for i in range(animations_count):
            parts = lines[current + i + 1].split(" ")
            animation = self._parse_animation(figure, parts)
            animations.append(animation)

        return animations

    def _parse_figure(self, line):
        parts = line.split(" ")
        if parts[0] == 'rectangle':
            center_x = float(parts[1])
            center_y = float(parts[2])
            width = float(parts[3])
            height = float(parts[4])
            angle = float(parts[5])
            color = parts[6].replace('\n', '')
            figure = Rectangle(center_x - width / 2, center_y - height / 2, width, height, color, angle)
        elif parts[0] == 'circle':
            center_x = float(parts[1])
            center_y = float(parts[2])
            radius = float(parts[3])
            color = parts[4].replace('\n', '')
            figure = Circle(center_x - radius, center_y - radius, radius, color)
        else:
            raise Exception()

        return figure

    def _parse_animation(self, figure, parts):
        if parts[0] == "move":
            animation = self._parse_move_animation(figure, parts)
        elif parts[0] == "scale":
            animation = self._parse_scale_animation(parts)
        elif parts[0] == "rotate":
            animation = self._parse_rotate_animation(parts)
        else:
            raise Exception()

        return animation

    @staticmethod
    def _parse_move_animation(figure, parts):
        to_x = float(parts[1])
        to_y = float(parts[2])
        time = float(parts[3])
        cycle = len(parts) >= 5
        return MoveAnimation(figure, to_x, to_y, time, cycle)

    @staticmethod
    def _parse_scale_animation(parts):
        destination_scale = float(parts[1])
        time = float(parts[2])
        cycle = len(parts) >= 4
        return ScaleAnimation(destination_scale, time, cycle)

    @staticmethod
    def _parse_rotate_animation(parts):
        rotate_angle = float(parts[1])
        time = float(parts[2])
        cycle = len(parts) >= 4
        return RotateAnimation(rotate_angle, time, cycle)


def main():
    canvas_width, canvas_height, animated_symbols = \
        AnimationsParser().parse_animated_symbols('animation_path.txt')

    window = tkinter.Tk()
    configure_window_location(window, canvas_width, canvas_height)

    canvas = tkinter.Canvas(window, width=canvas_width, height=canvas_height)
    scene = Scene(canvas, animated_symbols)

    timer = Timer()
    timer.start()

    window.after(TIME_BETWEEN_FRAMES, scene_loop, window, scene, timer)
    window.mainloop()


if __name__ == "__main__":
    main()

Формат ввода

Формат вывода

Пример

Примечания