Submission #19239868


Source Code Expand

Copy
import java.io.FileNotFoundException;
import java.util.Queue;
import java.util.InputMismatchException;
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
import java.util.stream.Collectors;
import java.io.FileInputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Random;
import java.util.Comparator;
import java.util.stream.StreamSupport;
import java.util.ArrayDeque;
import java.util.stream.IntStream;
import java.io.InputStream;
import java.io.IOException;
import java.util.PriorityQueue;

public class Main {
    private static final String LOG_TEMPLATE_FILE_NAME = System.getenv("ATCODER_ROOT_PATH") + "/src/main/java/toolkit_A_v20201218_2/log/%s.txt";
    public static Logger LOGGER;

    InputStream is;

    private static final Mode MODE = Mode.SUBMIT;
    private static final String __DEBUG_FILE_NAME__ = System.getenv("ATCODER_ROOT_PATH") + "/src/main/java/A-local-test.in";

    FastScanner in;
    PrintWriter out;

    public void solve() {
        final WorldA world = WorldA.createFromStdin(in);
        if (MODE == Mode.CREATE_FILE_DEBUG) {
            LOGGER.log(world.toOutput());
        }
        final SolverA solver = new NaiveSolverA();
        solver.initialize(world);
        final WeatherEvent[] weatherEvents = new WeatherEvent[world.g.size()];
        for (int turn = 0; turn < world.tMax; turn++) {
            final PowerResult[] powerResults = new PowerResult[world.getGridN()];
            for (int i = 0; i < world.getGridN(); i++) {
                final int x = in.nextInt() - 1;
                final int y = in.nextInt();
                final int powerActual = in.nextInt();
                final int powerExcess = in.nextInt();
                final int powerBuy = in.nextInt();
                powerResults[i] = new PowerResult(x, y, powerActual, powerExcess, powerBuy);

                if (world.powerPrediction.dayType == DayType.RAINY_WITH_SUNNY && powerActual - world.powerPrediction.getPower(world.getGrid(i), world.currentTurn) >= world.powerPrediction.deltaEvent * 0.6) {
                    weatherEvents[x] = WeatherEvent.UNEXPECTED_SUNNY;
                } else if (world.powerPrediction.dayType == DayType.SUNNY_GUERRILLA && world.powerPrediction.getPower(world.getGrid(i), world.currentTurn) - powerActual >= world.powerPrediction.deltaEvent * 0.6) {
                    weatherEvents[x] = WeatherEvent.UNEXPECTED_RAINY;
                } else {
                    weatherEvents[x] = WeatherEvent.NONE;
                }
            }
            final EvInfo[] carInfos = new EvInfo[world.getEvN()];
            for (int i = 0; i < world.getEvN(); i++) {
                final int charge = in.nextInt();
                final int u = in.nextInt() - 1;
                final int v = in.nextInt() - 1;
                final int distFromU = in.nextInt();
                final int distFromV = in.nextInt();

                final int nAdj = in.nextInt();
                final int[] a = new int[nAdj];
                for (int j = 0; j < nAdj; j++) {
                    a[j] = in.nextInt() - 1;
                }
                final EvPosition evPosition = new EvPosition(u, v, distFromU, distFromV);
                carInfos[i] = new EvInfo(charge, evPosition, a);
            }
            final TurnInfoA turnInfo = new TurnInfoA(powerResults, carInfos, weatherEvents);
            world.applyTurnInfo(turnInfo);
            final Commands commands = solver.solve(turnInfo);
            if (MODE == Mode.LOCAL_TEST) {
                LOGGER.log(turnInfo);
                LOGGER.log(commands.toAnswer());
            } else if (MODE == Mode.CREATE_FILE_DEBUG) {
                LOGGER.log(turnInfo.toString());
            }
            out.println(commands.toAnswer());
            out.flush();

            world.advanceTurn();
        }
        out.close();
    }

    public void run(String[] args) {
        if (MODE == Mode.FILE_DEBUG) {
            final String fileName = __DEBUG_FILE_NAME__;
            try {
                is = new FileInputStream(fileName);
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
            System.out.println("FILE_INPUT!");
        } else {
            is = System.in;
        }
        in = new FastScanner(is);
        out = new PrintWriter(System.out);
        if (MODE == Mode.LOCAL_TEST) {
            Preconditions.check(args.length == 1, "The first parameter must be file name of the log");
            solveWithLogging(String.format(LOG_TEMPLATE_FILE_NAME, args[0]));
        } else if (MODE == Mode.CREATE_FILE_DEBUG) {
            solveWithLogging(__DEBUG_FILE_NAME__);
        } else {
            solve();
        }
    }

    private void solveWithLogging(String logFileName) {
        try {
            LOGGER = Logger.create(logFileName);
            solve();
        } catch (Throwable e) {
            if (LOGGER != null) {
                LOGGER.logError(e);
            }
            throw new RuntimeException(e);
        } finally {
            if (LOGGER != null) {
                LOGGER.close();
            }
        }

    }

    public static void main(final String[] args) {
        new Main().run(args);
    }

    enum Mode {
        SUBMIT,
        LOCAL_TEST,
        FILE_DEBUG,
        CREATE_FILE_DEBUG;
    }
}


class EvInfo {
    public final int charge;
    public final EvPosition evPosition;
    public final int[] a;

    public EvInfo(int charge, EvPosition evPosition, int[] a) {
        this.charge = charge;
        this.evPosition = evPosition;
        this.a = a;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(charge).append("\n");
        res.append(evPosition.toString()).append("\n");
        if (a != null) {
            res.append(a.length).append(" ");
            for (int v : a) {
                res.append(v + 1).append(" ");
            }
        }
        return res.deleteCharAt(res.length() - 1).toString();
    }

    public EvInfo moveTo(final EvPosition newPosition) {
        return new EvInfo(charge, newPosition, a);
    }
}

enum WeatherEvent {
    NONE(0),
    UNEXPECTED_RAINY(-1),
    UNEXPECTED_SUNNY(1);

    private final int factor;

    WeatherEvent(int factor) {
        this.factor = factor;
    }

    public int getDelta(int deltaEvent) {
        return deltaEvent * factor;
    }
}


class TurnInfoA {
    public final PowerResult[] powerResults;
    public final EvInfo[] evInfos;
    public final WeatherEvent[] weatherEvents;

    public TurnInfoA(PowerResult[] powerResults, EvInfo[] evInfos, WeatherEvent[] weatherEvents) {
        this.powerResults = powerResults;
        this.evInfos = evInfos;
        this.weatherEvents = weatherEvents;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        for (PowerResult pr : powerResults) {
            res.append(pr.toString()).append("\n");
        }
        for (EvInfo evInfo : evInfos) {
            res.append(evInfo.toString()).append("\n");
        }
        return res.deleteCharAt(res.length() - 1).toString();
    }

    public boolean occurWeatherEvent() {
        return Arrays.stream(weatherEvents).anyMatch(weatherEvent -> weatherEvent != null && weatherEvent != WeatherEvent.NONE);
    }
}

class PowerResult {
    public final int x;
    public final int y;
    public final int powerActual;
    public final int powerExcess;
    public final int powerBuy;

    public PowerResult(int x, int y, int powerActual, int powerExcess, int powerBuy) {
        this.x = x;
        this.y = y;
        this.powerActual = powerActual;
        this.powerExcess = powerExcess;
        this.powerBuy = powerBuy;
    }

    @Override
    public String toString() {
        return (x+1) + " " + y + " " + powerActual + " " + powerExcess + " " + powerBuy;
    }
}


interface Command {
    String toAnswer();

    void apply(WorldA worldA);
}


class Commands {
    public final List<Command> commands;

    public Commands(List<Command> commands) {
        this.commands = commands;
    }

    public String toAnswer() {
        return commands.stream()
                .map(Command::toAnswer)
                .collect(Collectors.joining("\n"));
    }

    public void add(final Command command) {
        commands.add(command);
    }
}


class StayCommand implements Command {
    public static StayCommand SINGLETON = new StayCommand();

    private StayCommand() {
    }

    @Override
    public String toAnswer() {
        return "stay";
    }

    @Override
    public void apply(WorldA worldA) {

    }
}


class ChargeFromGridCommand implements Command {
    public final int evId;
    public final int deltaCharge;

    public ChargeFromGridCommand(int evId, int deltaCharge) {
        this.evId = evId;
        this.deltaCharge = deltaCharge;
    }

    @Override
    public String toAnswer() {
        return "charge_from_grid " + deltaCharge;
    }

    @Override
    public void apply(WorldA worldA) {

    }
}


class ChargeToGridCommand implements Command {
    public final int evId;
    public final int chargeDelta;

    public ChargeToGridCommand(int evId, int chargeDelta) {
        this.evId = evId;
        this.chargeDelta = chargeDelta;
    }

    @Override
    public String toAnswer() {
        return "charge_to_grid " + chargeDelta;
    }

    @Override
    public void apply(WorldA worldA) {

    }
}


class MoveCommand implements Command {
    public final int evId;
    public final int w;

    public MoveCommand(int evId, int w) {
        this.evId = evId;
        this.w = w;
    }

    @Override
    public String toAnswer() {
        return "move " + (w + 1);
    }

    @Override
    public void apply(WorldA worldA) {
        worldA.moveEv(evId, w);
    }

    @Override
    public String toString() {
        return "MoveCommand{" +
                "evId=" + evId +
                ", w=" + w +
                '}';
    }
}


class Logger {
    private static final boolean FLAG = false;

    final PrintWriter printWriter;

    private Logger(PrintWriter printWriter) {
        this.printWriter = printWriter;
    }

    public static Logger create(final String path) throws FileNotFoundException {
        return new Logger(new PrintWriter(path));
    }

    public void log(Object s) {
        printWriter.println(s);
    }

    void flush() {
        printWriter.flush();
    }

    public void close() {
        printWriter.close();
    }

    public void logError(Throwable e) {
        e.printStackTrace(printWriter);
    }
}



class StaySolverA implements SolverA {
    @Override
    public void initialize(WorldA worldA) {

    }

    @Override
    public Commands solve(TurnInfoA turnInfoA) {
        final ArrayList<Command> list = new ArrayList<>();
        for (int i = 0; i < turnInfoA.evInfos.length; i++) {
            list.add(StayCommand.SINGLETON);
        }
        return new Commands(list);
    }
}


interface SolverA {
    void initialize(final WorldA worldA);

    Commands solve(final TurnInfoA turnInfoA);
}



class NaiveSolverA implements SolverA {
    private WorldA worldA;

    Queue<Command[]> commandsQueue;
    int[] evToGridAllocation;

    @Override
    public void initialize(final WorldA worldA) {
        this.worldA = worldA;
        commandsQueue = new ArrayDeque<>();
    }

    private int[] assignEv(final TurnInfoA turnInfoA) {
        final PowerPrediction.Result[] predictionResults = worldA.predict(turnInfoA.weatherEvents);
        int[] evToGridAllocation = new int[worldA.getEvN()];
        List<Integer>[] gridToEvs = new ArrayList[worldA.getGridN()];
        Arrays.fill(evToGridAllocation, 0);
        for (int i = 0; i < worldA.getGridN(); i++) {
            gridToEvs[i] = new ArrayList<>();
        }
        for (int evId = 0; evId < worldA.getEvN(); evId++) {
            int minGridId = -1;
            int minDist = Integer.MAX_VALUE;
            final EvInfo evInfo = turnInfoA.evInfos[evId];
            for (int gridId = 0; gridId < worldA.getGridN(); gridId++) {
                final Grid grid = worldA.grids.grids[gridId];
                int nDist = worldA.getDistance(evInfo, grid.x);
                PowerPrediction.Result result = predictionResults[gridId];
                final int lossEnergy = result.getMinEnergy() + gridToEvs[gridId].stream().map(allocatedEvId -> worldA.evs.evs[allocatedEvId].charge).reduce(0, Integer::sum);
                final int excessEnergy = result.getMaxEnergy() - gridToEvs[gridId].stream().map(allocatedEvId -> worldA.evs.cEvMax - worldA.evs.evs[allocatedEvId].charge).reduce(0, Integer::sum);
                if (lossEnergy > 0 && excessEnergy <= grid.cGridMax) {
                    // continue;
                }
                if (nDist < minDist && evInfo.charge >= nDist * worldA.evs.deltaEvMove) {
                    minDist = nDist;
                    minGridId = gridId;
                }
            }
            if (minGridId != -1) {
                evToGridAllocation[evId] = minGridId;
                gridToEvs[minGridId].add(evId);
            }
        }
        return evToGridAllocation;
    }

    private int[] assignEv2(final TurnInfoA turnInfoA) {
        final PowerPrediction.Result[] predictionResults = worldA.predict(turnInfoA.weatherEvents);
        SAState current = SAState.create(worldA.getGridN(), assignEv(turnInfoA));
        int currentScore = calcScore(current,predictionResults);
        SAState best = current.copy();
        int bestScore = currentScore;

        final int TIME_CHECK_PHASE = 500;
        final int TIME_LIMIT_MS = 2000;
        final SATemperature saTemperature = new SATemperature(100, 0.01, 10000, TIME_LIMIT_MS);

        int totalCount = 0;
        int count = TIME_CHECK_PHASE;
        long currentTime = 0;
        final TimeKeeper timeKeeper = new TimeKeeper();
        while (true) {
            if (count-- == 0) {
                if (timeKeeper.getPassedTime() >= TIME_LIMIT_MS) {
                    break;
                }
                totalCount += TIME_CHECK_PHASE;
                count = TIME_CHECK_PHASE;
            }
            current.transit();

            int nextScore = calcScore(current, predictionResults);
            if (nextScore < bestScore) {
                System.err.println("Best update: " + bestScore + " => " + nextScore);
                bestScore = nextScore;
                best = current.copy();
            } else if (saTemperature.forceNext(currentTime, bestScore - nextScore)) {
                // System.err.println("Force update: " + bestScore + ", " + nextScore);
            } else {
                current.undo();
            }
        }
        System.err.println("Trial count: " + totalCount);
        return best.evToGridAllocation;
    }

    int[] lossEnergy = new int[100];
    int[] excessEnergy = new int[100];

    private int calcScore(SAState state, PowerPrediction.Result[] results) {
        int score = 0;
        final int turn = Math.min(worldA.tMax, worldA.currentTurn.getCurrentTurn() + worldA.currentTurn.getPhase() * 10);
        for (int gridId = 0; gridId < worldA.getGridN(); gridId++) {
            lossEnergy[gridId] = results[gridId].getMinEnergy(turn);
            excessEnergy[gridId] = results[gridId].getMaxEnergy(turn);
        }
        for (int evId = 0; evId < worldA.getEvN(); evId++) {
            final int gridId = state.evToGridAllocation[evId];
            final int dist = worldA.getDistance(worldA.evs.evs[evId], worldA.grids.grids[gridId].x);
            final int expectedCharge = worldA.evs.evs[evId].charge + dist * worldA.evs.deltaEvMove;
            lossEnergy[state.evToGridAllocation[evId]] += expectedCharge - worldA.evs.cEvMax / 20;
            excessEnergy[state.evToGridAllocation[evId]] -= worldA.evs.cEvMax - expectedCharge;
        }
        for (int gridId = 0; gridId < worldA.getGridN(); gridId++) {
            score += Math.max(-lossEnergy[gridId], 0);
            score += Math.max(excessEnergy[gridId] - worldA.grids.cGridMax, 0);
        }

        for (int evId = 0; evId < worldA.getEvN(); evId++) {
            final int gridId = state.evToGridAllocation[evId];
            final long nDist = worldA.getDistance(worldA.evs.evs[evId], worldA.grids.grids[gridId].x);
            score += nDist * worldA.evs.deltaEvMove;
            if (worldA.evs.evs[evId].charge < nDist * worldA.evs.deltaEvMove * 1.5) {
                score += 1000000;
            }
        }
        return score;
    }

    private Queue<Command[]> buildCommandQueue(int[] evToGridAllocation) {
        final ArrayDeque<Command[]> commandsQueue = new ArrayDeque<>();
        final int turnCount = worldA.currentTurn.turnCountPerPhase + (worldA.currentTurn.getCurrentTurn() == 0 ? 1 : worldA.currentTurn.isLastPhase() ? -1 : 0);
        for (int t = 0; t < turnCount; t++) {
            final Command[] commandArray = new Command[worldA.getEvN()];
            Arrays.fill(commandArray, StayCommand.SINGLETON);
            for (int evId = 0; evId < worldA.getEvN(); evId++) {
                if (evToGridAllocation[evId] == -1) {
                    continue;
                }
                final int gridId = evToGridAllocation[evId];
                final EvInfo evInfo = worldA.evs.evs[evId];
                final Grid grid = worldA.grids.grids[gridId];
                if (!evInfo.evPosition.isAt(grid.x)) {
                    commandArray[evId] = new MoveCommand(evId, worldA.graphDistance.findNextPos(evInfo.evPosition, grid.x));
                }
            }
            Arrays.stream(commandArray).forEach(command -> command.apply(worldA));
            commandsQueue.add(commandArray);
        }
        return commandsQueue;
    }

    @Override
    public Commands solve(final TurnInfoA turnInfoA) {
        if (worldA.currentTurn.isPhaseUpdated()) {
            Preconditions.check(commandsQueue == null || commandsQueue.isEmpty());
            evToGridAllocation = assignEv2(turnInfoA);
            commandsQueue = buildCommandQueue(evToGridAllocation);
        }
        Preconditions.check(!commandsQueue.isEmpty());
        Command[] nextCommands = commandsQueue.poll();
        // TODO: Chargeつめる。vEvMaxとcEvMaxを存在するevの数を考慮しながらchargeするなど
        for (int evId = 0; evId < worldA.getEvN(); evId++) {
            if (evToGridAllocation[evId] == -1) {
                continue;
            }
            final int gridId = evToGridAllocation[evId];
            final EvInfo evInfo = worldA.evs.evs[evId];
            final Grid grid = worldA.grids.grids[gridId];
            if (!(nextCommands[evId] instanceof StayCommand) || !evInfo.evPosition.isAt(grid.x)) {
                continue;
            }
            final WeatherEvent weatherEvent = turnInfoA.weatherEvents[grid.x];
            final PowerResult powerResult = turnInfoA.powerResults[gridId];
            if (weatherEvent == WeatherEvent.UNEXPECTED_RAINY || powerResult.y < grid.cGridMax * 0.2) {
                final int chargeAmount;
                if (weatherEvent == WeatherEvent.UNEXPECTED_RAINY) {
                    chargeAmount = Math.min(turnInfoA.evInfos[evId].charge, worldA.evs.vEvMax);
                } else {
                    chargeAmount = Math.min(turnInfoA.evInfos[evId].charge, worldA.evs.vEvMax / 2);
                }
                if (chargeAmount > 0 && (worldA.currentTurn.isLastPhase() || turnInfoA.evInfos[evId].charge - chargeAmount > worldA.evs.cEvMax / 20)) {
                    nextCommands[evId] = new ChargeToGridCommand(evId, chargeAmount);
                }
            } else if (weatherEvent == WeatherEvent.UNEXPECTED_SUNNY || powerResult.y > grid.cGridMax * 0.8) {
                final int chargeAmount;
                if (weatherEvent == WeatherEvent.UNEXPECTED_SUNNY) {
                    chargeAmount = Math.min(worldA.evs.cEvMax - turnInfoA.evInfos[evId].charge, worldA.evs.vEvMax);
                } else {
                    chargeAmount = Math.min(worldA.evs.cEvMax - turnInfoA.evInfos[evId].charge, worldA.evs.vEvMax / 2);
                }
                if (chargeAmount > 0) {
                    nextCommands[evId] = new ChargeFromGridCommand(evId, chargeAmount);
                }
            }
        }
        return new Commands(Arrays.asList(nextCommands));
    }

    static class SAState {
        private static final Random RANDOM = new Random(123);

        final int[] evToGridAllocation;
        final int[] gridToEvAllocation;

        private Transit prevTransit;

        public SAState(int[] evToGridAllocation, int[] gridToEvAllocation) {
            this.evToGridAllocation = evToGridAllocation;
            this.gridToEvAllocation = gridToEvAllocation;
            prevTransit = null;
        }

        public static SAState create(int gridN, int[] evToGridAllocation) {
            int[] gridToEvAllocation = new int[gridN];
            for (int evId = 0; evId < evToGridAllocation.length; evId++) {
                final int gridId = evToGridAllocation[evId];
                gridToEvAllocation[gridId] |= (1 << evId);
            }
            return new SAState(Arrays.copyOf(evToGridAllocation, evToGridAllocation.length), gridToEvAllocation);
        }

        public SAState copy() {
            return new SAState(Arrays.copyOf(evToGridAllocation, evToGridAllocation.length), Arrays.copyOf(gridToEvAllocation, gridToEvAllocation.length));
        }

        public void transit() {
            final Transit transit = createTransitRandomly();

            final int evBit = (1 << transit.evId);
            evToGridAllocation[transit.evId] = transit.gridId;
            Preconditions.check((gridToEvAllocation[transit.gridId] & evBit) == 0);
            Preconditions.check((gridToEvAllocation[transit.prevGridId] & evBit) == evBit);
            gridToEvAllocation[transit.gridId] |= evBit;
            gridToEvAllocation[transit.prevGridId] ^= evBit;

            prevTransit = transit;
        }

        public void undo() {
            Preconditions.check(prevTransit != null);
            evToGridAllocation[prevTransit.evId] = prevTransit.prevGridId;
            final int evBit = (1 << prevTransit.evId);
            Preconditions.check((gridToEvAllocation[prevTransit.gridId] & evBit) == evBit);
            Preconditions.check((gridToEvAllocation[prevTransit.prevGridId] & evBit) == 0);
            gridToEvAllocation[prevTransit.gridId] ^= evBit;
            gridToEvAllocation[prevTransit.prevGridId] |= evBit;

            prevTransit = null;
        }

        private Transit createTransitRandomly() {
            int evId;
            int gridId;
            do {
                evId = RANDOM.nextInt(evToGridAllocation.length);
                gridId = RANDOM.nextInt(gridToEvAllocation.length);
            } while (evToGridAllocation[evId] == gridId);
            return new Transit(evId, gridId, evToGridAllocation[evId]);
        }

        public boolean existsEvInGrid(int gridId, int evId) {
            return (gridToEvAllocation[gridId] & (1 << evId)) != 0;
        }
    }

    static class Transit {
        final int evId;
        final int gridId;
        final int prevGridId;

        public Transit(int evId, int gridId, int prevGridId) {
            this.evId = evId;
            this.gridId = gridId;
            this.prevGridId = prevGridId;
        }
    }
}


class FastScanner {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public FastScanner(InputStream stream) {
        this.stream = stream;
        // stream = new FileInputStream(new File("dec.in"));
    }

    int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public boolean isEndline(int c) {
        return c == '\n' || c == '\r' || c == -1;
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public int[] nextIntArray(int n) {
        int[] array = new int[n];
        for (int i = 0; i < n; i++)
            array[i] = nextInt();

        return array;
    }

    public int[][] nextIntMap(int n, int m) {
        int[][] map = new int[n][m];
        for (int i = 0; i < n; i++) {
            map[i] = nextIntArray(m);
        }
        return map;
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public long[] nextLongArray(int n) {
        long[] array = new long[n];
        for (int i = 0; i < n; i++)
            array[i] = nextLong();

        return array;
    }

    public long[][] nextLongMap(int n, int m) {
        long[][] map = new long[n][m];
        for (int i = 0; i < n; i++) {
            map[i] = nextLongArray(m);
        }
        return map;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public double[] nextDoubleArray(int n) {
        double[] array = new double[n];
        for (int i = 0; i < n; i++)
            array[i] = nextDouble();

        return array;
    }

    public double[][] nextDoubleMap(int n, int m) {
        double[][] map = new double[n][m];
        for (int i = 0; i < n; i++) {
            map[i] = nextDoubleArray(m);
        }
        return map;
    }

    public String next() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    public String[] nextStringArray(int n) {
        String[] array = new String[n];
        for (int i = 0; i < n; i++)
            array[i] = next();

        return array;
    }

    public String nextLine() {
        int c = read();
        while (isEndline(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isEndline(c));
        return res.toString();
    }

    public int[][] nextPackedIntArrays(int packN, int size) {
        int[][] res = new int[packN][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < packN; j++) {
                res[j][i] = nextInt();
            }
        }
        return res;
    }
}

class Preconditions {
    public static void check(boolean x) {
        check(x, "");
    }

    public static void check(boolean x, String message) {
        if (!x) {
            throw new IllegalArgumentException(message);
        }
    }

}


class Grids {
    public final Grid[] grids;
    public final int cGridInit;
    public final int cGridMax;
    public final int vGridMax;

    private Grids(Grid[] grids, int cGridInit, int cGridMax, int vGridMax) {
        this.grids = grids;
        this.cGridInit = cGridInit;
        this.cGridMax = cGridMax;
        this.vGridMax = vGridMax;
    }

    public static Grids createFromStdin(final FastScanner in) {
        final int nGrid = in.nextInt();
        final int cGridInit = in.nextInt();
        final int cGridMax = in.nextInt();
        final int vGridMax = in.nextInt();

        final Grid[] grid = new Grid[nGrid];
        for (int i = 0; i < nGrid; i++) {
            final int x = in.nextInt() - 1;
            final int patternId = in.nextInt() - 1;
            grid[i] = new Grid(x, patternId, cGridInit, cGridMax, vGridMax, cGridInit);
        }
        return new Grids(grid, cGridInit, cGridMax, vGridMax);
    }

    public int size() {
        return grids.length;
    }

    public String toOutput() {
        final StringBuilder sb = new StringBuilder();
        sb.append(grids.length).append(" ")
                .append(cGridInit).append(" ")
                .append(cGridMax).append(" ")
                .append(vGridMax).append("\n");
        for (int i = 0; i < grids.length; i++) {
            sb.append(grids[i].x + 1).append(" ").append(grids[i].patternId + 1).append("\n");
        }
        return sb.toString();
    }

    public void updateEnergy(PowerResult[] powerResults) {
        for (int i = 0; i < grids.length; i++) {
            final Grid grid = grids[i];
            grids[i] = new Grid(grid.x, grid.patternId, grid.cGridInit, grid.cGridMax, grid.vGridMax, powerResults[i].y);
        }
    }
}

class Turn {
    public final int turnCountPerPhase;
    public final int phaseNum;
    private int currentTurn;

    public Turn(int turnCountPerPhase, int phaseNum, int currentTurn) {
        this.turnCountPerPhase = turnCountPerPhase;
        this.phaseNum = phaseNum;
        this.currentTurn = currentTurn;
    }

    public void advanceTurn() {
        currentTurn++;
    }

    public int getPhase() {
        return getPhaseInternal(currentTurn);
    }

    private int getPhaseInternal(final int turn) {
        return turn / turnCountPerPhase;
    }

    public boolean isPhaseUpdated() {
        if (currentTurn == 0) {
            return true;
        }
        if (currentTurn == 1) {
            return false;
        }
        final int prevPhase2 = getPhaseInternal(currentTurn - 2);
        final int prevPhase = getPhaseInternal(currentTurn - 1);
        final int currentPhase = getPhaseInternal(currentTurn);
        return prevPhase2 + 1 == currentPhase && prevPhase == currentPhase;
    }

    public boolean isLastPhase() {
        return getPhaseInternal(currentTurn) == phaseNum - 1;
    }

    public int getCurrentTurn() {
        return currentTurn;
    }
}



class WorldA {
    public final Graph<Edge> g;
    public final PowerPrediction powerPrediction;
    public final Grids grids;
    public final EVs evs;
    public final GraphDistance graphDistance;

    public final double gamma;
    public final int tMax;

    public Turn currentTurn;

    public WorldA(Graph<Edge> g, PowerPrediction powerPrediction, Grids grids, EVs evs, GraphDistance graphDistance, double gamma, int tMax) {
        this.g = g;
        this.powerPrediction = powerPrediction;
        this.grids = grids;
        this.evs = evs;
        this.graphDistance = graphDistance;
        this.gamma = gamma;
        this.tMax = tMax;

        currentTurn = new Turn(tMax / powerPrediction.nDiv, powerPrediction.nDiv, 0);
    }

    public static WorldA createFromStdin(final FastScanner in) {
        final Graph<Edge> g = GraphUtil.createFromStdIn(in);
        final PowerPrediction powerPrediction = PowerPrediction.createFromStdin(in);
        final Grids grids = Grids.createFromStdin(in);
        final EVs evs = EVs.createFromStdin(in);
        final double gamma = in.nextDouble();
        final int tMax = in.nextInt();
        final GraphDistance graphDistance = GraphDistance.create(g);
        return new WorldA(g, powerPrediction, grids, evs, graphDistance, gamma, tMax);
    }

    public String toOutput() {
        return GraphUtil.toOutput(g) +
                powerPrediction.toOutput() +
                grids.toOutput() +
                evs.toOutput() +
                gamma + " " + tMax;
    }

    public int getGridN() {
        return grids.size();
    }

    public int getEvN() {
        return evs.size();
    }

    public Grid getGrid(int i) {
        return grids.grids[i];
    }

    public int findNextPos(EvPosition evPosition, int x) {
        return graphDistance.findNextPos(evPosition, x);
    }

    public void moveEv(final int evId, final int next) {
        final EvPosition evPosition = evs.evs[evId].evPosition;
        if (evPosition.isSame()) {
            Edge e = null;
            for (Edge ne : g.edges(evPosition.u)) {
                if (ne.to() == next) {
                    e = ne;
                }
            }
            Preconditions.check(e != null);
            if (e.cost() == 1) {
                evs.evs[evId] = evs.evs[evId].moveTo(new EvPosition(next, next, 0, 0));
            } else {
                evs.evs[evId] = evs.evs[evId].moveTo(new EvPosition(evPosition.u, next, 1, (int) e.cost() - 1));
            }
        } else {
            evs.evs[evId] = evs.evs[evId].moveTo(evPosition.moveTo(next));
        }
    }

    public int getDistance(EvInfo evInfo, int x) {
        if (evInfo.evPosition.isSame()) {
            return graphDistance.dist(evInfo.evPosition.u, x);
        } else {
            final int distFromU = graphDistance.dist(evInfo.evPosition.u, x) + evInfo.evPosition.distFromU;
            final int distFromV = graphDistance.dist(evInfo.evPosition.v, x) + evInfo.evPosition.distFromV;
            return Math.min(distFromU, distFromV);
        }
    }

    public PowerPrediction.Result[] predict(WeatherEvent[] weatherEvents) {
        return Arrays.stream(grids.grids)
                .map(grid -> powerPrediction.predict(grid, grid.currentEnergy, currentTurn, tMax, weatherEvents[grid.x]))
                .toArray(PowerPrediction.Result[]::new);
    }

    public void applyTurnInfo(TurnInfoA turnInfo) {
        grids.updateEnergy(turnInfo.powerResults);
        evs.updateEnergy(turnInfo.evInfos);
    }

    public void advanceTurn() {
        currentTurn.advanceTurn();
    }
}

enum DayType {
    SUNNY(0),
    SUNNY_GUERRILLA(1),
    RAINY(2),
    RAINY_WITH_SUNNY(3);

    public final int id;

    DayType(int id) {
        this.id = id;
    }

    public static DayType fromId(int id) {
        for (DayType dayType: values()) {
            if (dayType.id == id) {
                return dayType;
            }
        }
        throw new IllegalArgumentException();
    }
}

class Grid {
    public final int x;
    public final int patternId;
    public final int cGridInit;
    public final int cGridMax;
    public final int vGridMax;
    public final int currentEnergy;

    public Grid(int x, int patternId, int cGridInit, int cGridMax, int vGridMax, int currentEnergy) {
        this.x = x;
        this.patternId = patternId;
        this.cGridInit = cGridInit;
        this.cGridMax = cGridMax;
        this.vGridMax = vGridMax;
        this.currentEnergy = currentEnergy;
    }
}


class EVs {
    public final int cEvInit;
    public final int cEvMax;
    public final int vEvMax;
    public final int deltaEvMove;
    public final EvInfo[] evs;

    public EVs(int cEvInit, int cEvMax, int vEvMax, int deltaEvMove, EvInfo[] evs) {
        this.cEvInit = cEvInit;
        this.cEvMax = cEvMax;
        this.vEvMax = vEvMax;
        this.deltaEvMove = deltaEvMove;
        this.evs = evs;
    }

    public static EVs createFromStdin(final FastScanner in) {
        final int nEv = in.nextInt();
        final int cEvInit = in.nextInt();
        final int cEvMax = in.nextInt();
        final int vEvMax = in.nextInt();
        final int deltaEvMove = in.nextInt();
        final EvInfo[] evs = new EvInfo[nEv];
        for (int i = 0; i < nEv; i++) {
            final int pos = in.nextInt() - 1;
            evs[i] = new EvInfo(cEvInit, new EvPosition(pos, pos, 0, 0), null);
        }
        return new EVs(cEvInit, cEvMax, vEvMax, deltaEvMove, evs);
    }

    public int size() {
        return evs.length;
    }

    public String toOutput() {
        final StringBuilder sb = new StringBuilder();
        sb.append(evs.length).append(" ")
                .append(cEvInit).append(" ")
                .append(cEvMax).append(" ")
                .append(vEvMax).append(" ")
                .append(deltaEvMove).append("\n");
        for (int i = 0; i < evs.length; i++) {
            sb.append(evs[i].evPosition.u + 1).append("\n");
        }
        return sb.toString();
    }

    public void updateEnergy(EvInfo[] evInfos) {
        for (int i = 0; i < evs.length; i++) {
            evs[i] = evInfos[i];
        }
    }
}


class EvPosition {
    public final int u;
    public final int v;
    public final int distFromU;
    public final int distFromV;

    public EvPosition(int u, int v, int distFromU, int distFromV) {
        this.u = u;
        this.v = v;
        this.distFromU = distFromU;
        this.distFromV = distFromV;
    }

    @Override
    public String toString() {
        return (u+1) + " " + (v+1) + " " + distFromU + " " + distFromV;
    }

    public boolean isAt(int x) {
        return x == u && x == v;
    }

    public EvPosition moveTo(int next) {
        Preconditions.check(u != v);
        Preconditions.check(u == next || v == next);
        if (u == next) {
            if (distFromU == 1) {
                return new EvPosition(u, u, 0, 0);
            } else {
                return new EvPosition(u, v, distFromU - 1, distFromV + 1);
            }
        } else {
            if (distFromV == 1) {
                return new EvPosition(v, v, 0, 0);
            } else {
                return new EvPosition(u, v, distFromU + 1, distFromV - 1);
            }
        }
    }

    public boolean isSame() {
        return u == v;
    }
}


class TimeKeeper {
    public static final int SECTYPE_SEC = 0;
    public static final int SECTYPE_MSEC = 1;

    private final int MAX_LOOP_SIZE = 100;

    private long startTime;
    ArrayList<Long> pushedTime = new ArrayList<Long>();
    private long[] totalLoopTime = new long[MAX_LOOP_SIZE];
    private long[] prevPushedTime = new long[MAX_LOOP_SIZE];

    public TimeKeeper() {
        reset();
    }

    public void reset() {
        startTime = System.currentTimeMillis();
        Arrays.fill(totalLoopTime, 0);
        Arrays.fill(prevPushedTime, 0);
        pushedTime.clear();
        push();
    }

    public void push() {
        pushedTime.add(System.currentTimeMillis());
    }

    public void loopPush(int id) {
        assert prevPushedTime[id] == 0;
        prevPushedTime[id] = System.currentTimeMillis();
    }

    public void loopPop(int id) {
        assert prevPushedTime[id] != 0;
        long current = System.currentTimeMillis();
        totalLoopTime[id] += current - prevPushedTime[id];
        prevPushedTime[id] = 0;
    }
    @Override
    public String toString() {
        String res = "";
        {
            res += "---------- Nomal pushed time -----------------\n";
            double totalTime = 0;
            for (int i = 0; i < pushedTime.size() - 1; i++) {
                double time = (pushedTime.get(i + 1) - pushedTime.get(i)) / 1000.0;
                totalTime += time;
                res += i + " : " + time + "s\n";
            }
            res += "Total Time = " + totalTime + "s\n";
        }

        {
            res += "----------- Loop pushed time -----------------\n";
            double totalTime = 0;
            for (int i = 0; i < MAX_LOOP_SIZE; i++) {
                if (totalLoopTime[i] != 0) {
                    res += "Loop " + i + " : " + (totalLoopTime[i]/1000.0) + "s\n";
                    totalTime += totalLoopTime[i]/1000.0;
                }
            }
            res += "Total Loop Time = " + totalTime + "s\n";
        }
        return res;
    }

    public long getPassedTime() {
        return System.currentTimeMillis() - startTime;
    }

    public String getPassedTimeSecond(int type) {
        switch (type) {
            case SECTYPE_SEC :
                return (getPassedTime() / 1000.0) + "s";
            case SECTYPE_MSEC :
                return getPassedTime() + "ms";
        }

        throw new RuntimeException();
    }
}


class XorShift {
    private static final double toDouble = 1.0 / 2147483648.0;
    private int w = 88675123;
    private int x = 123456789;
    private int y = 362436069;
    private int z = 521288629;
    private int count = 0;

    public XorShift() {
        x = (int) System.nanoTime();
    }

    public XorShift(long l) {
        x = (int) l;
    }

    public int getCount() {
        return count;
    }

    public double nextDouble() {
        return (nextInt() & Integer.MAX_VALUE) * toDouble;
    }

    public int nextInt() {
        count++;
        final int t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
        return w;
    }

    public int nextInt(int n) {
        return (int) (n * nextDouble());
    }

    public long nextLong() {
        long a = nextInt();
        long b = nextInt();
        return (a << 32) ^ b;
    }
}

class SATemperature {
    private static final XorShift rnd = new XorShift(123321);

    private final double startTemperature;
    private final double endTemperature;
    private final int maxTemperature;
    private final int timeLimitMs;

    public SATemperature(double startTemperature, double endTemperature, int maxTemperature, int timeLimitMs) {
        this.startTemperature = startTemperature;
        this.endTemperature = endTemperature;
        this.maxTemperature = maxTemperature;
        this.timeLimitMs = timeLimitMs;
    }

    public boolean forceNext(long currentTime, double scoreDiff) {
        double temp = startTemperature + ((endTemperature - startTemperature) * currentTime) / timeLimitMs;
        double limit = (double)(rnd.nextInt(maxTemperature) + 1) / maxTemperature;
        double probability = Math.exp(scoreDiff / temp);
        return probability > limit;
    }
}



class PowerPrediction {
    public final DayType dayType;
    public final int nDiv;
    public final int nPattern;
    public final int electricSupplySigma;
    public final double pEvent;
    public final int deltaEvent;
    public final int[][] powerPredict;

    private PowerPrediction(DayType dayType, int nDiv, int nPattern, int electricSupplySigma, double pEvent, int deltaEvent, int[][] powerPredict) {
        this.dayType = dayType;
        this.nDiv = nDiv;
        this.nPattern = nPattern;
        this.electricSupplySigma = electricSupplySigma;
        this.pEvent = pEvent;
        this.deltaEvent = deltaEvent;
        this.powerPredict = powerPredict;
    }

    public static PowerPrediction createFromStdin(final FastScanner in) {
        final DayType dayType = DayType.fromId(in.nextInt());
        final int nDiv = in.nextInt();
        final int nPattern = in.nextInt();
        final int electricSupplySigma = in.nextInt();
        final double pEvent = in.nextDouble();
        final int deltaEvent = in.nextInt();
        final int[][] powerPredict = in.nextIntMap(nPattern, nDiv);
        return new PowerPrediction(dayType, nDiv, nPattern, electricSupplySigma / 10, pEvent, deltaEvent, powerPredict);
    }

    public String toOutput() {
        final StringBuilder sb = new StringBuilder();
        sb.append(dayType.id).append(" ")
                .append(nDiv).append(" ")
                .append(nPattern).append(" ")
                .append(electricSupplySigma).append(" ")
                .append(pEvent).append(" ")
                .append(deltaEvent).append("\n");
        for (int i = 0; i < nPattern; i++) {
            for (int j = 0; j < nDiv; j++) {
                sb.append(powerPredict[i][j]).append(" ");
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    public Result predict(final Grid grid, final int gridCapacity, final Turn turn, final int tMax, final WeatherEvent weatherEvent) {
        int[] energy = new int[tMax+1];
        int[] minEnergy = new int[tMax+1];
        int[] maxEnergy = new int[tMax+1];
        int[] excess = new int[tMax+1];
        int[] loss = new int[tMax+1];

        final int startTurn = turn.getPhase() * turn.turnCountPerPhase;

        int curEnergy = gridCapacity;
        energy[startTurn] = gridCapacity;
        minEnergy[startTurn] = gridCapacity;
        maxEnergy[startTurn] = gridCapacity;
        for (int i = startTurn; i < tMax; i++) {
            int t = i / turn.turnCountPerPhase;
            energy[i+1] = energy[i] + powerPredict[grid.patternId][t];
            curEnergy += powerPredict[grid.patternId][t] + (t == turn.getPhase() ? weatherEvent.getDelta(deltaEvent) : 0);
            minEnergy[i+1] = Math.min(minEnergy[i], curEnergy);
            maxEnergy[i+1] = Math.max(maxEnergy[i], curEnergy);
            if (energy[i+1] > grid.cGridMax) {
                excess[i+1] = grid.cGridMax - energy[i+1];
                energy[i+1] = grid.cGridMax;
            }
            if (energy[i+1] < 0) {
                loss[i+1] = -energy[i+1];
                energy[i+1] = 0;
            }
        }
        return Result.create(energy, excess, loss, minEnergy, maxEnergy);
    }

    public int getPower(Grid grid, Turn currentTurn) {
        return powerPredict[grid.patternId][currentTurn.getPhase()];
    }

    public static class Result {
        public final int[] energy;
        public final int[] excess;
        public final int[] loss;
        public final int[] minEnergy;
        public final int[] maxEnergy;

        public final int totalExcess;
        public final int totalLoss;

        public Result(int[] energy, int[] excess, int[] loss, int[] minEnergy, int[] maxEnergy, int totalExcess, int totalLoss) {
            this.energy = energy;
            this.excess = excess;
            this.loss = loss;
            this.minEnergy = minEnergy;
            this.maxEnergy = maxEnergy;
            this.totalExcess = totalExcess;
            this.totalLoss = totalLoss;
        }

        public static Result create(int[] energy, int[] excess, int[] loss, int[] minEnergy, int[] maxEnergy) {
            final int totalLoss = Arrays.stream(loss).reduce(0, Integer::sum);
            final int totalExcess = Arrays.stream(excess).reduce(0, Integer::sum);
            return new Result(energy, excess, loss, minEnergy, maxEnergy, totalExcess, totalLoss);
        }

        public int getMinEnergy() {
            return minEnergy[minEnergy.length - 1];
        }

        public int getMaxEnergy() {
            return maxEnergy[maxEnergy.length - 1];
        }

        public int getMinEnergy(int turn) {
            return minEnergy[turn];
        }

        public int getMaxEnergy(int turn) {
            return maxEnergy[turn];
        }
    }
}

class SimpleEdge implements Edge {
    private final int to;

    public SimpleEdge(int to) {
        this.to = to;
    }

    @Override
    public int to() {
        return to;
    }

    @Override
    public long cost() {
        return 1;
    }
}

interface CappedEdge extends Edge {
    long cap();

    CappedEdge rev();

    void addCap(long cap);
}


class Graph<E extends Edge> {
    private final int n;
    private final List<E>[] g;

    public static <E extends Edge> Graph<E> create(int n) {
        @SuppressWarnings("unchecked")
        ArrayList<E>[] l = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            l[i] = new ArrayList<>();
        }
        return new Graph<>(n, l);
    }

    public Graph(int n, List<E>[] g) {
        this.n = n;
        this.g = g;
    }

    public static Graph<SimpleEdge> createDirectionalTree(int[] a, int[] b) {
        if (a.length != b.length) {
            throw new IllegalArgumentException("len(a) != len(b)");
        }
        int n = a.length + 1;
        Graph<SimpleEdge> g = create(n);
        for (int i = 0; i < n - 1; i++) {
            g.addDirectionalEdge(a[i], new SimpleEdge(b[i]));
        }
        return g;
    }

    public static Graph<SimpleEdge> createUndirectionalTree(int[] a, int[] b, boolean oneOrigin) {
        if (a.length != b.length) {
            throw new IllegalArgumentException("len(a) != len(b)");
        }
        int n = a.length + 1;
        Graph<SimpleEdge> g = create(n);

        int adjust = oneOrigin ? 1 : 0;
        for (int i = 0; i < n - 1; i++) {
            g.addDirectionalEdge(a[i] - adjust, new SimpleEdge(b[i] - adjust));
            g.addDirectionalEdge(b[i] - adjust, new SimpleEdge(a[i] - adjust));
        }
        return g;
    }

    public void addDirectionalEdge(int u, E e) {
        g[u].add(e);
    }

    public List<E> edges(int u) {
        return g[u];
    }

    public int edgeNum(int u) {
        return g[u].size();
    }

    public int totalEndgeNum() {
        return Arrays.stream(g)
                .map(List::size)
                .reduce(0, Integer::sum) / 2;
    }

    public int size() {
        return n;
    }

    /**
     *
     * @param start
     * @return The cost of node v is:
     * <ul>
     *     <li>-(1L << 62) if a node is under negative loop</li>
     *     <li>(1L << 62) if there is no edge to v</li>
     *     <li>otherwise minimum cost from node u to a node</li>
     * </ul>
     */
    public long[] bellmanford(int start) {
        final long INF = 1L << 62;
        long[] dist = new long[n];
        Arrays.fill(dist, INF);
        dist[start] = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int u = 0; u < n; u++) {
                for (Edge e : edges(u)) {
                    dist[e.to()] = Math.min(dist[e.to()], dist[u] + e.cost());
                }
            }
        }

        long[] res = Arrays.copyOf(dist, dist.length);
        for (int i = 0; i < n; i++) {
            for (int u = 0; u < n; u++) {
                for (Edge e : edges(u)) {
                    int v = e.to();
                    if (res[u] + e.cost() < res[v]) {
                        res[v] = -INF;
                    }
                }
            }
        }
        return res;
    }

    /**
     *
     * @param start
     * @return For each v, true if a node v can be arrived from start node, otherwise false.
     */
    public boolean[] canArrive(int start) {
        boolean[] res = new boolean[size()];
        canArriveInternal(start, res);
        return res;
    }

    private void canArriveInternal(int u, boolean[] visited) {
        visited[u] = true;
        for (Edge e : edges(u)) {
            if (visited[e.to()]) {
                continue;
            }
            canArriveInternal(e.to(), visited);
        }
    }

    public DiameterResult diameter() {
        if (totalEndgeNum() != n - 1) {
            throw new IllegalArgumentException("Graph should be tree");
        }
        int[] parents = new int[size()];
        int[] dist = new int[size()];
        Arrays.fill(dist, -1);
        dfs(0, dist, parents, 0);

        int x = 0;
        for (int i = 1; i < size(); i++) {
            if (dist[x] < dist[i]) {
                x = i;
            }
        }

        int[] dist2 = new int[size()];
        Arrays.fill(dist2, -1);
        parents[x] = x;
        dfs(x, dist2, parents, 0);

        int best = 0;
        for (int i = 0; i < n; i++) {
            if (dist2[best] < dist2[i]) {
                best = i;
            }
        }
        return new DiameterResult(restore(x, best, parents), dist2[best] + 1);
    }

    private int[] restore(int from, int to, int[] parents) {
        List<Integer> pathL = new ArrayList<>();
        int cur = to;
        while (cur != from) {
            pathL.add(cur);
            cur = parents[cur];
        }
        pathL.add(from);

        int[] res = new int[pathL.size()];
        for (int i = 0; i < pathL.size(); i++) {
            res[i] = pathL.get(pathL.size() - i - 1);
        }
        return res;
    }

    private void dfs(int u, int[] dist, int[] parent, int depth) {
        dist[u] = depth;
        for (Edge e : g[u]) {
            if (dist[e.to()] != -1) {
                continue;
            }
            parent[e.to()] = u;
            dfs(e.to(), dist, parent, depth + 1);
        }
    }

    public static class DiameterResult {
        public final int[] path;
        public final int dist;

        public DiameterResult(int[] path, int dist) {
            this.path = path;
            this.dist = dist;
        }

        @Override
        public String toString() {
            return "DiameterResult{" +
                    "path=" + Arrays.toString(path) +
                    ", dist=" + dist +
                    '}';
        }
    }

    /**
     * Assuming edge is SimpleEdge
     * @param start
     * @return
     */
    public int[] bfs(int start) {
        int n = g.length;
        int[] dist = new int[n];
        Arrays.fill(dist, 1 << 30);
        dist[start] = 0;

        Queue<Integer> q = new ArrayDeque<>();
        q.add(start);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (Edge e : g[u]) {
                if (dist[e.to()] == 1 << 30) {
                    dist[e.to()] = dist[u] + 1;
                    q.add(e.to());
                }
            }
        }
        return dist;
    }
}

class EdgeImpl implements Edge {
    private final int to;
    private final long cost;

    public EdgeImpl(int to, long cost) {
        this.to = to;
        this.cost = cost;
    }

    @Override
    public int to() {
        return to;
    }

    @Override
    public long cost() {
        return cost;
    }
}

interface EdgeGenerator<E extends Edge> {
    E generate(int to, E originalEdge);
}

class CappedEdgeImpl implements CappedEdge {
    final int to;
    final long cost;

    private long cap;
    private CappedEdge rev;

    private CappedEdgeImpl(int to, long cost, long cap) {
        this.to = to;
        this.cost = cost;
        this.cap = cap;
    }

    public static class CappedEdgePair {
        public final CappedEdge normal;
        public final CappedEdge rev;

        public CappedEdgePair(CappedEdge normal, CappedEdge rev) {
            this.normal = normal;
            this.rev = rev;
        }
    }

    public static CappedEdgePair pairedEdges(int from, int to, long cap, long cost) {
        CappedEdgeImpl e = new CappedEdgeImpl(to, cost, cap);
        CappedEdgeImpl revE = new CappedEdgeImpl(from, -cost, 0);
        e.rev = revE;
        revE.rev = e;
        return new CappedEdgePair(e, revE);
    }

    public static CappedEdgePair pairedEdgesForMaxFlow(int from, int to, long cap) {
        return pairedEdges(from, to, cap, Long.MAX_VALUE);
    }

    @Override
    public int to() {
        return to;
    }

    @Override
    public long cost() {
        return cost;
    }

    @Override
    public long cap() {
        return cap;
    }

    @Override
    public CappedEdge rev() {
        return rev;
    }

    @Override
    public void addCap(long cap) {
        this.cap += cap;
    }
}

interface Edge {
    int to();

    long cost();
}



class GraphDistance {
    private static final int INF = 1 << 20;

    private final int[][] distance;
    private final int[][] next;
    private final int[][] prev;

    public GraphDistance(int[][] distance, int[][] next, int[][] prev) {
        this.distance = distance;
        this.next = next;
        this.prev = prev;
    }

    public static GraphDistance create(final Graph<? extends Edge> g) {
        final int n = g.size();
        final int[][] dist = new int[n][n];
        final int[][] next = new int[n][n];
        final int[][] prev = new int[n][n];
        for (int u = 0; u < n; u++) {
            Arrays.fill(dist[u], INF);
            for (Edge e : g.edges(u)) {
                int v = e.to();
                dist[u][v] = (int) e.cost();
                next[u][v] = v;
                prev[u][v] = u;
            }
            dist[u][u] = 0;
            next[u][u] = -1;
            prev[u][u] = -1;
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        next[i][j] = next[i][k];
                        prev[i][j] = prev[k][j];
                    }
                }
            }
        }
        return new GraphDistance(dist, next, prev);
    }

    public int findNextPos(EvPosition evPosition, int x) {
        if (evPosition.u == evPosition.v) {
            return next[evPosition.u][x];
        }
        final int du = evPosition.distFromU + distance[evPosition.u][x];
        final int dv = evPosition.distFromV + distance[evPosition.v][x];
        if (du < dv) {
            return evPosition.u;
        } else {
            return evPosition.v;
        }
    }

    public int next(final int u, final int v) {
        return next[u][v];
    }

    public int dist(final int u, final int v) {
        return distance[u][v];
    }
}



class GraphUtil {
    private GraphUtil() {
    }

    public static Graph<Edge> createFromStdIn(final FastScanner in) {
        final int V = in.nextInt();
        final int E = in.nextInt();
        final Graph<Edge> g = Graph.create(V);
        for (int i = 0; i < E; i++) {
            int u = in.nextInt() - 1;
            int v = in.nextInt() - 1;
            int d = in.nextInt();
            g.addDirectionalEdge(u, new EdgeImpl(v, d));
            g.addDirectionalEdge(v, new EdgeImpl(u, d));
        }
        return g;
    }

    public static String toOutput(Graph<Edge> g) {
        StringBuilder sb = new StringBuilder();
        sb.append(g.size()).append(" ").append(IntStream.range(0, g.size()).map(g::edgeNum).reduce(0, Integer::sum)).append("\n");
        for (int u = 0; u < g.size(); u++) {
            for (Edge e : g.edges(u)) {
                sb.append(u + 1).append(" ")
                        .append(e.to() + 1).append(" ")
                        .append(e.cost()).append("\n");
            }
        }
        return sb.toString();
    }
}


class DijkstraResult {
    public final long[] minDist;
    public final int[] prevNodes;
    public final int[] prevEdges;

    public DijkstraResult(long[] minDist, int[] prevNodes, int[] prevEdges) {
        this.minDist = minDist;
        this.prevNodes = prevNodes;
        this.prevEdges = prevEdges;
    }

    public int[] path(int start, int goal) {
        Stack<Integer> stack = new Stack<>();
        for (int cur = goal; cur != start; cur = prevNodes[cur]) {
            stack.add(cur);
        }
        stack.add(start);

        int[] res = new int[stack.size()];
        int ptr = 0;
        while (!stack.isEmpty()) {
            res[ptr++] = stack.pop();
        }
        return res;
    }
}



class Dijkstra {
    public static final long INF = 1L << 60;

    final Graph<? extends Edge> g;

    public Dijkstra(Graph<? extends Edge> g) {
        this.g = g;
    }

    public DijkstraResult doit(int start) {
        int[] prevNodes = new int[g.size()];
        int[] prevEdges = new int[g.size()];
        long[] minDist = new long[g.size()];
        Arrays.fill(minDist, INF);
        minDist[start] = 0;
        prevNodes[start] = prevEdges[start] = -1;

        PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingLong(st -> st.cost));
        pq.add(new State(0, start));

        while (!pq.isEmpty()) {
            State st = pq.poll();
            if (minDist[st.u] < st.cost) {
                continue;
            }

            List<? extends Edge> es = g.edges(st.u);
            for (int i = 0; i < es.size(); i++) {
                Edge e = es.get(i);
                long ncost = minDist[st.u] + e.cost();
                if (minDist[e.to()] > ncost) {
                    minDist[e.to()] = ncost;
                    prevNodes[e.to()] = st.u;
                    prevEdges[e.to()] = i;
                    pq.add(new State(minDist[e.to()], e.to()));
                }
            }
        }
        return new DijkstraResult(minDist, prevNodes, prevEdges);
    }

    private class State {
        final long cost;
        final int u;

        public State(long cost, int u) {
            this.cost = cost;
            this.u = u;
        }
    }
}

Submission Info

Submission Time
Task A - hokudai_hitachi2020_a
User hiro116s
Language Java (OpenJDK 11.0.6)
Score 49906427
Code Size 61997 Byte
Status AC
Exec Time 43533 ms
Memory 80608 KB

Compile Error

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Judge Result

Set Name All
Score / Max Score 49906427 / 9999999999999
Status
AC × 16
Set Name Test Cases
All test_case_1, test_case_10, test_case_11, test_case_12, test_case_13, test_case_14, test_case_15, test_case_16, test_case_2, test_case_3, test_case_4, test_case_5, test_case_6, test_case_7, test_case_8, test_case_9
Case Name Status Exec Time Memory
test_case_1 AC 43492 ms 63388 KB
test_case_10 AC 43464 ms 61324 KB
test_case_11 AC 43507 ms 80068 KB
test_case_12 AC 43484 ms 60860 KB
test_case_13 AC 43521 ms 78848 KB
test_case_14 AC 43525 ms 80004 KB
test_case_15 AC 43533 ms 78808 KB
test_case_16 AC 43468 ms 63120 KB
test_case_2 AC 43516 ms 78352 KB
test_case_3 AC 43517 ms 62040 KB
test_case_4 AC 43528 ms 80608 KB
test_case_5 AC 43481 ms 60548 KB
test_case_6 AC 43483 ms 60588 KB
test_case_7 AC 43491 ms 59564 KB
test_case_8 AC 43528 ms 80116 KB
test_case_9 AC 43464 ms 61700 KB