oj.uz

Submission #254789

# Submission time Handle Problem Language Result Execution time Memory
254789 2020-07-30T15:25:13 Z model_code Graph (BOI20_graph) Java 11
100 / 100
 475 ms 34208 KB 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Graph {

    static StreamTokenizer in;
    static PrintWriter out;

    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    final static int MAXN = 200005;

    static int n, m;

    static int[] a = new int[MAXN];
    static int[] b = new int[MAXN];
    static int[] c = new int[MAXN];
    static int[] deg = new int[MAXN];

    static int[] gptr = new int[2 * MAXN];
    static int[] gfst = new int[2 * MAXN];
    static int[] gsnd = new int[2 * MAXN];

    static boolean[] vis = new boolean[MAXN];
    static int[] sgn = new int[MAXN];
    static int[] val = new int[MAXN];

    static int Ql, Qr;
    static int[] Q = new int[MAXN];

    static int ans[] = new int[MAXN];

    static int cnt;
    static int comp[] = new int[MAXN];

    static int num[] = new int[MAXN];

    static int quickSelect(int l, int r, int k) {
        if (l == r) {
            return num[l];
        }
        int pivot = num[r];
        int ptrL = l;
        int ptrR = r;
        for (int i = l; i <= ptrR; i++) {
            if (num[i] < pivot) {
                if (ptrL < i) {
                    int tmp = num[ptrL];
                    num[ptrL] = num[i];
                    num[i] = tmp;
                }
                ptrL++;
            } else if (num[i] > pivot) {
                int tmp = num[ptrR];
                num[ptrR] = num[i];
                num[i] = tmp;
                ptrR--;
                i--;
            }
        }
        if (k < ptrL) {
            return quickSelect(l, ptrL - 1, k);
        } else if (k > ptrR) {
            return quickSelect(ptrR + 1, r, k);
        } else {
            return pivot;
        }
    }

    public static void main(String[] args) throws IOException {
        in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);

        n = nextInt();
        m = nextInt();
        for (int i = 0; i < m; i++) {
            a[i] = nextInt();
            b[i] = nextInt();
            c[i] = 2 * nextInt();
            deg[a[i]]++;
            deg[b[i]]++;
        }

        for (int v = 1; v <= n; v++) {
            deg[v] += deg[v - 1];
            gptr[v] = deg[v - 1];
        }

        for (int i = 0; i < m; i++) {
            gfst[gptr[a[i]]] = b[i];
            gsnd[gptr[a[i]]] = c[i];
            gptr[a[i]]++;
            gfst[gptr[b[i]]] = a[i];
            gsnd[gptr[b[i]]] = c[i];
            gptr[b[i]]++;
        }

        for (int u = 1; u <= n; u++) {
            if (!vis[u]) {
                vis[u] = true;
                sgn[u] = +1;
                val[u] = 0;
                cnt = 0;
                comp[cnt++] = u;
                boolean bip = true;
                int x = 0;
                Ql = Qr = 0;
                Q[Qr++] = u;
                while (Ql < Qr) {
                    int v = Q[Ql++];
                    for (int i = deg[v - 1]; i < deg[v]; i++) {
                        int w = gfst[i];
                        int sum = gsnd[i];
                        if (!vis[w]) {
                            vis[w] = true;
                            sgn[w] = -sgn[v];
                            val[w] = sum - val[v];
                            comp[cnt++] = w;
                            Q[Qr++] = w;
                        } else if (sgn[w] == sgn[v]) {
                            bip = false;
                            x = sgn[w] * (sum - val[w] - val[v]) / 2;
                        }
                    }
                }

                if (bip) {
                    for (int i = 0; i < cnt; i++) {
                        int v = comp[i];
                        num[i] = (-sgn[v]) * val[v];
                    }
                    x = quickSelect(0, cnt - 1, cnt / 2);
                }

                for (int i = 0; i < cnt; i++) {
                    int v = comp[i];
                    ans[v] = val[v] + sgn[v] * x;
                }

                for (int i = 0; i < cnt; i++) {
                    int v = comp[i];
                    for (int j = deg[v - 1]; j < deg[v]; j++) {
                        int w = gfst[j];
                        if (ans[v] + ans[w] != gsnd[j]) {
                            out.println("NO");
                            out.flush();
                            return;
                        }
                    }
                }
            }
        }

        out.println("YES");
        for (int v = 1; v <= n; v++) {
            if(ans[v] == -1) {
                out.print("-");
            }
            out.print(ans[v] / 2);
            if (ans[v] % 2 != 0) {
                out.print(".5");
            }
            out.print(" ");
        }
        out.println();

        out.flush();
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 22904 KB answer = YES
2 Correct 76 ms 23036 KB answer = YES
3 Correct 76 ms 22776 KB answer = YES
4 Correct 76 ms 22856 KB answer = NO
5 Correct 78 ms 22904 KB answer = YES
6 Correct 79 ms 22776 KB answer = YES
7 Correct 82 ms 23096 KB answer = YES
8 Correct 85 ms 23064 KB answer = YES
9 Correct 76 ms 23032 KB answer = NO
10 Correct 78 ms 22776 KB answer = YES
11 Correct 76 ms 22904 KB answer = YES
12 Correct 79 ms 23012 KB answer = NO
13 Correct 78 ms 22904 KB answer = YES
14 Correct 77 ms 22904 KB answer = YES
15 Correct 78 ms 22904 KB answer = YES
16 Correct 78 ms 22644 KB answer = YES
17 Correct 84 ms 22724 KB answer = YES
18 Correct 83 ms 22904 KB answer = YES
19 Correct 88 ms 23036 KB answer = YES
20 Correct 86 ms 22712 KB answer = YES
21 Correct 86 ms 22900 KB answer = YES
22 Correct 83 ms 22896 KB answer = NO
23 Correct 90 ms 22884 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 22904 KB answer = YES
2 Correct 76 ms 23036 KB answer = YES
3 Correct 76 ms 22776 KB answer = YES
4 Correct 76 ms 22856 KB answer = NO
5 Correct 78 ms 22904 KB answer = YES
6 Correct 79 ms 22776 KB answer = YES
7 Correct 82 ms 23096 KB answer = YES
8 Correct 85 ms 23064 KB answer = YES
9 Correct 76 ms 23032 KB answer = NO
10 Correct 78 ms 22776 KB answer = YES
11 Correct 76 ms 22904 KB answer = YES
12 Correct 79 ms 23012 KB answer = NO
13 Correct 78 ms 22904 KB answer = YES
14 Correct 77 ms 22904 KB answer = YES
15 Correct 78 ms 22904 KB answer = YES
16 Correct 78 ms 22644 KB answer = YES
17 Correct 84 ms 22724 KB answer = YES
18 Correct 83 ms 22904 KB answer = YES
19 Correct 88 ms 23036 KB answer = YES
20 Correct 86 ms 22712 KB answer = YES
21 Correct 86 ms 22900 KB answer = YES
22 Correct 83 ms 22896 KB answer = NO
23 Correct 90 ms 22884 KB answer = NO
24 Correct 90 ms 22920 KB answer = YES
25 Correct 87 ms 22976 KB answer = YES
26 Correct 90 ms 22904 KB answer = YES
27 Correct 87 ms 22868 KB answer = YES
28 Correct 82 ms 22876 KB answer = YES
29 Correct 87 ms 23092 KB answer = YES
30 Correct 79 ms 22980 KB answer = NO
31 Correct 85 ms 22880 KB answer = YES
32 Correct 85 ms 22868 KB answer = YES
33 Correct 88 ms 22688 KB answer = YES
34 Correct 88 ms 22744 KB answer = YES
35 Correct 88 ms 22804 KB answer = YES
36 Correct 89 ms 23016 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 22904 KB answer = YES
2 Correct 76 ms 23036 KB answer = YES
3 Correct 76 ms 22776 KB answer = YES
4 Correct 76 ms 22856 KB answer = NO
5 Correct 78 ms 22904 KB answer = YES
6 Correct 79 ms 22776 KB answer = YES
7 Correct 82 ms 23096 KB answer = YES
8 Correct 85 ms 23064 KB answer = YES
9 Correct 76 ms 23032 KB answer = NO
10 Correct 78 ms 22776 KB answer = YES
11 Correct 76 ms 22904 KB answer = YES
12 Correct 79 ms 23012 KB answer = NO
13 Correct 78 ms 22904 KB answer = YES
14 Correct 77 ms 22904 KB answer = YES
15 Correct 78 ms 22904 KB answer = YES
16 Correct 78 ms 22644 KB answer = YES
17 Correct 84 ms 22724 KB answer = YES
18 Correct 83 ms 22904 KB answer = YES
19 Correct 88 ms 23036 KB answer = YES
20 Correct 86 ms 22712 KB answer = YES
21 Correct 86 ms 22900 KB answer = YES
22 Correct 83 ms 22896 KB answer = NO
23 Correct 90 ms 22884 KB answer = NO
24 Correct 90 ms 22920 KB answer = YES
25 Correct 87 ms 22976 KB answer = YES
26 Correct 90 ms 22904 KB answer = YES
27 Correct 87 ms 22868 KB answer = YES
28 Correct 82 ms 22876 KB answer = YES
29 Correct 87 ms 23092 KB answer = YES
30 Correct 79 ms 22980 KB answer = NO
31 Correct 85 ms 22880 KB answer = YES
32 Correct 85 ms 22868 KB answer = YES
33 Correct 88 ms 22688 KB answer = YES
34 Correct 88 ms 22744 KB answer = YES
35 Correct 88 ms 22804 KB answer = YES
36 Correct 89 ms 23016 KB answer = YES
37 Correct 93 ms 24068 KB answer = YES
38 Correct 93 ms 24112 KB answer = YES
39 Correct 92 ms 23988 KB answer = YES
40 Correct 99 ms 24288 KB answer = YES
41 Correct 101 ms 24380 KB answer = NO
42 Correct 121 ms 25016 KB answer = YES
43 Correct 97 ms 24116 KB answer = YES
44 Correct 121 ms 24428 KB answer = YES
45 Correct 115 ms 24360 KB answer = YES
46 Correct 105 ms 24072 KB answer = YES
47 Correct 113 ms 24204 KB answer = YES
48 Correct 105 ms 24856 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 22904 KB answer = YES
2 Correct 76 ms 23036 KB answer = YES
3 Correct 76 ms 22776 KB answer = YES
4 Correct 76 ms 22856 KB answer = NO
5 Correct 78 ms 22904 KB answer = YES
6 Correct 79 ms 22776 KB answer = YES
7 Correct 82 ms 23096 KB answer = YES
8 Correct 85 ms 23064 KB answer = YES
9 Correct 76 ms 23032 KB answer = NO
10 Correct 78 ms 22776 KB answer = YES
11 Correct 76 ms 22904 KB answer = YES
12 Correct 79 ms 23012 KB answer = NO
13 Correct 78 ms 22904 KB answer = YES
14 Correct 77 ms 22904 KB answer = YES
15 Correct 78 ms 22904 KB answer = YES
16 Correct 78 ms 22644 KB answer = YES
17 Correct 84 ms 22724 KB answer = YES
18 Correct 83 ms 22904 KB answer = YES
19 Correct 88 ms 23036 KB answer = YES
20 Correct 86 ms 22712 KB answer = YES
21 Correct 86 ms 22900 KB answer = YES
22 Correct 83 ms 22896 KB answer = NO
23 Correct 90 ms 22884 KB answer = NO
24 Correct 90 ms 22920 KB answer = YES
25 Correct 87 ms 22976 KB answer = YES
26 Correct 90 ms 22904 KB answer = YES
27 Correct 87 ms 22868 KB answer = YES
28 Correct 82 ms 22876 KB answer = YES
29 Correct 87 ms 23092 KB answer = YES
30 Correct 79 ms 22980 KB answer = NO
31 Correct 85 ms 22880 KB answer = YES
32 Correct 85 ms 22868 KB answer = YES
33 Correct 88 ms 22688 KB answer = YES
34 Correct 88 ms 22744 KB answer = YES
35 Correct 88 ms 22804 KB answer = YES
36 Correct 89 ms 23016 KB answer = YES
37 Correct 93 ms 24068 KB answer = YES
38 Correct 93 ms 24112 KB answer = YES
39 Correct 92 ms 23988 KB answer = YES
40 Correct 99 ms 24288 KB answer = YES
41 Correct 101 ms 24380 KB answer = NO
42 Correct 121 ms 25016 KB answer = YES
43 Correct 97 ms 24116 KB answer = YES
44 Correct 121 ms 24428 KB answer = YES
45 Correct 115 ms 24360 KB answer = YES
46 Correct 105 ms 24072 KB answer = YES
47 Correct 113 ms 24204 KB answer = YES
48 Correct 105 ms 24856 KB answer = YES
49 Correct 193 ms 27112 KB answer = YES
50 Correct 220 ms 27116 KB answer = YES
51 Correct 206 ms 27292 KB answer = YES
52 Correct 164 ms 25244 KB answer = NO
53 Correct 104 ms 24232 KB answer = YES
54 Correct 112 ms 23712 KB answer = YES
55 Correct 142 ms 25276 KB answer = YES
56 Correct 196 ms 26020 KB answer = YES
57 Correct 180 ms 27072 KB answer = YES
58 Correct 180 ms 26372 KB answer = YES
59 Correct 208 ms 27096 KB answer = YES
60 Correct 227 ms 26876 KB answer = YES
61 Correct 141 ms 24744 KB answer = YES
62 Correct 304 ms 25944 KB answer = NO
63 Correct 318 ms 26476 KB answer = YES
64 Correct 301 ms 26512 KB answer = NO
65 Correct 306 ms 26180 KB answer = YES
66 Correct 106 ms 24312 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 22904 KB answer = YES
2 Correct 76 ms 23036 KB answer = YES
3 Correct 76 ms 22776 KB answer = YES
4 Correct 76 ms 22856 KB answer = NO
5 Correct 78 ms 22904 KB answer = YES
6 Correct 79 ms 22776 KB answer = YES
7 Correct 82 ms 23096 KB answer = YES
8 Correct 85 ms 23064 KB answer = YES
9 Correct 76 ms 23032 KB answer = NO
10 Correct 78 ms 22776 KB answer = YES
11 Correct 76 ms 22904 KB answer = YES
12 Correct 79 ms 23012 KB answer = NO
13 Correct 78 ms 22904 KB answer = YES
14 Correct 77 ms 22904 KB answer = YES
15 Correct 78 ms 22904 KB answer = YES
16 Correct 78 ms 22644 KB answer = YES
17 Correct 84 ms 22724 KB answer = YES
18 Correct 83 ms 22904 KB answer = YES
19 Correct 88 ms 23036 KB answer = YES
20 Correct 86 ms 22712 KB answer = YES
21 Correct 86 ms 22900 KB answer = YES
22 Correct 83 ms 22896 KB answer = NO
23 Correct 90 ms 22884 KB answer = NO
24 Correct 90 ms 22920 KB answer = YES
25 Correct 87 ms 22976 KB answer = YES
26 Correct 90 ms 22904 KB answer = YES
27 Correct 87 ms 22868 KB answer = YES
28 Correct 82 ms 22876 KB answer = YES
29 Correct 87 ms 23092 KB answer = YES
30 Correct 79 ms 22980 KB answer = NO
31 Correct 85 ms 22880 KB answer = YES
32 Correct 85 ms 22868 KB answer = YES
33 Correct 88 ms 22688 KB answer = YES
34 Correct 88 ms 22744 KB answer = YES
35 Correct 88 ms 22804 KB answer = YES
36 Correct 89 ms 23016 KB answer = YES
37 Correct 93 ms 24068 KB answer = YES
38 Correct 93 ms 24112 KB answer = YES
39 Correct 92 ms 23988 KB answer = YES
40 Correct 99 ms 24288 KB answer = YES
41 Correct 101 ms 24380 KB answer = NO
42 Correct 121 ms 25016 KB answer = YES
43 Correct 97 ms 24116 KB answer = YES
44 Correct 121 ms 24428 KB answer = YES
45 Correct 115 ms 24360 KB answer = YES
46 Correct 105 ms 24072 KB answer = YES
47 Correct 113 ms 24204 KB answer = YES
48 Correct 105 ms 24856 KB answer = YES
49 Correct 193 ms 27112 KB answer = YES
50 Correct 220 ms 27116 KB answer = YES
51 Correct 206 ms 27292 KB answer = YES
52 Correct 164 ms 25244 KB answer = NO
53 Correct 104 ms 24232 KB answer = YES
54 Correct 112 ms 23712 KB answer = YES
55 Correct 142 ms 25276 KB answer = YES
56 Correct 196 ms 26020 KB answer = YES
57 Correct 180 ms 27072 KB answer = YES
58 Correct 180 ms 26372 KB answer = YES
59 Correct 208 ms 27096 KB answer = YES
60 Correct 227 ms 26876 KB answer = YES
61 Correct 141 ms 24744 KB answer = YES
62 Correct 304 ms 25944 KB answer = NO
63 Correct 318 ms 26476 KB answer = YES
64 Correct 301 ms 26512 KB answer = NO
65 Correct 306 ms 26180 KB answer = YES
66 Correct 106 ms 24312 KB answer = YES
67 Correct 449 ms 33392 KB answer = YES
68 Correct 389 ms 32196 KB answer = YES
69 Correct 352 ms 33028 KB answer = YES
70 Correct 423 ms 31396 KB answer = YES
71 Correct 353 ms 33236 KB answer = YES
72 Correct 381 ms 31776 KB answer = YES
73 Correct 364 ms 32144 KB answer = YES
74 Correct 307 ms 29892 KB answer = YES
75 Correct 262 ms 25720 KB answer = NO
76 Correct 216 ms 27064 KB answer = YES
77 Correct 211 ms 28140 KB answer = YES
78 Correct 333 ms 31184 KB answer = YES
79 Correct 328 ms 30952 KB answer = YES
80 Correct 315 ms 30464 KB answer = YES
81 Correct 252 ms 26928 KB answer = NO
82 Correct 357 ms 32720 KB answer = YES
83 Correct 342 ms 33696 KB answer = YES
84 Correct 475 ms 34208 KB answer = YES
85 Correct 329 ms 31824 KB answer = YES
86 Correct 340 ms 33868 KB answer = YES
87 Correct 283 ms 26292 KB answer = NO
88 Correct 386 ms 34012 KB answer = YES
89 Correct 395 ms 32476 KB answer = YES
90 Correct 414 ms 33692 KB answer = YES
91 Correct 413 ms 33620 KB answer = YES
92 Correct 349 ms 31636 KB answer = YES
93 Correct 332 ms 30524 KB answer = YES
94 Correct 287 ms 27096 KB answer = NO
95 Correct 219 ms 25456 KB answer = NO
96 Correct 413 ms 32972 KB answer = YES
97 Correct 229 ms 25652 KB answer = NO