Submission #254789

#	Time	Username	Problem	Language	Result	Execution time	Memory
254789		model_code	Graph (BOI20_graph)	Java	100 / 100	475 ms	34208 KiB

Graph

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 / 5
• Subtask 2: 12 / 12
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 42 / 42