Submission #255307

#	Time	Username	Problem	Language	Result	Execution time	Memory
255307		model_code	Aesthetic (NOI20_aesthetic)	Java	20 / 100	2094 ms	116376 KiB

Aesthetic

import java.io.*;
import java.util.*;

public class Aesthetic {

    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
    }
    static class Pf4 implements Comparable<Pf4>{
        long one;
        int two,three,four;
        Pf4(long a, int b, int c, int d){
            this.one = a;
            this.two = b;
            this.three = c;
            this.four = d;
        }
        public int compareTo(Pf4 x){
            if(this.one!=x.one){
                if(this.one>x.one)return 1;
                else return -1;
            }
            if(this.two!=x.two)return this.two - x.two;
            if(this.three!=x.three)return this.three - x.three;
            return this.four - x.four;

        }
    }
    static class Pf3 implements Comparable<Pf3>{
        int two,three,one;
        Pf3(int a, int b, int c){
            this.one = a;
            this.two = b;
            this.three = c;
        }
        public int compareTo(Pf3 x){
            if(this.one!=x.one)return this.one - x.one;
            if(this.two!=x.two)return this.two - x.two;
            return this.three - x.three;

        }
    }
    static int[][] A = new int[300000][4];
    static long[][] r = new long[2][300000];
    static boolean[] vt = new boolean[300000], f = new boolean[300000];
    static int[] p = new int[300000], q = new int[300000], d = new int[300000], id = new int[300000];
    static ArrayList<Pf3>[] adj = new ArrayList[300000];
    static PriorityQueue<Pf4> pq = new PriorityQueue<Pf4>(11);//, new Pf4(0,0,0,0));

    static int frt(int i) {if (i == id[i]) {return i;} else {return id[i] = frt(id[i]);}}

    static void it(int i, int t, int o, int l, long v) {
     //   System.err.println("! " + i + " " + t + " " + o + " " + l + " " + v);
        if (vt[i]) return;
        vt[i] = true;
        if (t == 0) {p[i] = o; q[i] = l; d[i] = d[o] + (i > 0 ? 1 : 0);}
        r[t][i] = v;
        for (int j = 0; j < adj[i].size(); ++j) if (!vt[adj[i].get(j).one]) pq.offer(new Pf4(v + adj[i].get(j).two, adj[i].get(j).one,i, adj[i].get(j).three));
    }

    public static void main(String args[]) throws IOException {
        Reader reader = new Reader();
        int N = reader.nextInt(), M = reader.nextInt(), a, b, x, i, j;
        long l, h = 300000000000000L, c;
        boolean e;
        for (i = 0; i < N; ++i) adj[i] = new ArrayList<Pf3>();
        for (i = 0; i < M; ++i) {for (j = 0; j < 3; ++j) A[i][j] = reader.nextInt(); adj[--A[i][0]].add(new Pf3(--A[i][1], A[i][2], i)); adj[A[i][1]].add(new Pf3(A[i][0], A[i][2], i));}
        for (i = M - 2; i > -1; --i) A[i][3] = Math.max(A[i + 1][2], A[i + 1][3]);
        it(0, 0, 0, -1, 0);
        while (pq.size() > 0) {x = pq.peek().two; c = pq.peek().one; a = pq.peek().three; b = pq.peek().four; pq.poll(); it(x, 0, a, b, c);}
        for (i = 0; i < N; ++i) vt[i] = false;
        it(N - 1, 1, N - 1, -1, 0);
        while (pq.size() > 0) {x = pq.peek().two; c = pq.peek().one; a = pq.peek().three; b = pq.peek().four; pq.poll(); it(x, 1, a, b, c);}
        l = r[0][N - 1];
        while (l < h) {
            e = false;
            c = (l + h + 1) / 2;
            System.err.println("? " + l + " " + h + ": " + c);
            for (i = 0; i < N; ++i) {id[i] = p[i]; if (i > 0) f[q[i]] = true;}
            for (i = N - 1; i > 0; i = p[i]) id[i] = i;
            for (i = 0; i < M; ++i) if (!f[i] && (r[0][A[i][0]] + A[i][2] + r[1][A[i][1]] < c || r[0][A[i][1]] + A[i][2] + r[1][A[i][0]] < c)) {
                a = frt(A[i][0]);
                b = frt(A[i][1]);
                if (d[a] > d[b]) {a ^= b; b ^= a; a ^= b;}
                while (a != b) {id[b] = p[b]; b = frt(b);}
            }
            for (i = frt(N - 1); i > 0 && !e; i = frt(p[i])) e = (c <= r[0][A[q[i]][0]] + A[q[i]][2] + A[q[i]][3] + r[1][A[q[i]][1]] && c <= r[0][A[q[i]][1]] + A[q[i]][2] + A[q[i]][3] + r[1][A[q[i]][0]]);
            if (e) l = c;
            else h = c - 1;
        }
        System.out.print((l + h) / 2);
    }
}

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 0 / 15
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22
• Subtask 7: 0 / 27