oj.uz

Submission #255307

# Submission time Handle Problem Language Result Execution time Memory
255307 2020-07-31T17:15:14 Z model_code Aesthetic (NOI20_aesthetic) Java 11
20 / 100
 2000 ms 116376 KB 
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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 31948 KB Output is correct
2 Correct 121 ms 32024 KB Output is correct
3 Correct 125 ms 31980 KB Output is correct
4 Correct 114 ms 32088 KB Output is correct
5 Correct 119 ms 32080 KB Output is correct
6 Correct 116 ms 32096 KB Output is correct
7 Correct 117 ms 32116 KB Output is correct
8 Correct 110 ms 31992 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 31948 KB Output is correct
2 Correct 121 ms 32024 KB Output is correct
3 Correct 125 ms 31980 KB Output is correct
4 Correct 114 ms 32088 KB Output is correct
5 Correct 119 ms 32080 KB Output is correct
6 Correct 116 ms 32096 KB Output is correct
7 Correct 117 ms 32116 KB Output is correct
8 Correct 110 ms 31992 KB Output is correct
9 Correct 157 ms 34416 KB Output is correct
10 Correct 171 ms 34700 KB Output is correct
11 Correct 172 ms 34404 KB Output is correct
12 Correct 184 ms 34424 KB Output is correct
13 Correct 182 ms 35176 KB Output is correct
14 Correct 162 ms 34572 KB Output is correct
15 Correct 150 ms 34408 KB Output is correct
16 Correct 157 ms 34332 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1659 ms 113784 KB Output is correct
2 Correct 1896 ms 116376 KB Output is correct
3 Correct 1802 ms 114216 KB Output is correct
4 Correct 1791 ms 113660 KB Output is correct
5 Correct 1604 ms 114756 KB Output is correct
6 Correct 1973 ms 114944 KB Output is correct
7 Correct 1842 ms 114760 KB Output is correct
8 Correct 1839 ms 116356 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2012 ms 115832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2094 ms 109796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2094 ms 109796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 31948 KB Output is correct
2 Correct 121 ms 32024 KB Output is correct
3 Correct 125 ms 31980 KB Output is correct
4 Correct 114 ms 32088 KB Output is correct
5 Correct 119 ms 32080 KB Output is correct
6 Correct 116 ms 32096 KB Output is correct
7 Correct 117 ms 32116 KB Output is correct
8 Correct 110 ms 31992 KB Output is correct
9 Correct 157 ms 34416 KB Output is correct
10 Correct 171 ms 34700 KB Output is correct
11 Correct 172 ms 34404 KB Output is correct
12 Correct 184 ms 34424 KB Output is correct
13 Correct 182 ms 35176 KB Output is correct
14 Correct 162 ms 34572 KB Output is correct
15 Correct 150 ms 34408 KB Output is correct
16 Correct 157 ms 34332 KB Output is correct
17 Correct 1659 ms 113784 KB Output is correct
18 Correct 1896 ms 116376 KB Output is correct
19 Correct 1802 ms 114216 KB Output is correct
20 Correct 1791 ms 113660 KB Output is correct
21 Correct 1604 ms 114756 KB Output is correct
22 Correct 1973 ms 114944 KB Output is correct
23 Correct 1842 ms 114760 KB Output is correct
24 Correct 1839 ms 116356 KB Output is correct
25 Execution timed out 2012 ms 115832 KB Time limit exceeded
26 Halted 0 ms 0 KB -