Submission #254794

#	Time	Username	Problem	Language	Result	Execution time	Memory
254794		model_code	Village (BOI20_village)	Java	100 / 100	450 ms	33804 KiB

Village

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Village {

    static int masa[] = new int[100000];
    static int masb[] = new int[100000];

    static int degree[] = new int[100001];
    static long neighboursum[] = new long[100001];
    static int rinda[] = new int[100000];
    static int subtree[] = new int[100001];
    static int place[] = new int[100001];
    static int fatchild[] = new int[100001];
    static int order[] = new int[100000];
    static int place2[] = new int[100001];
    static int group[] = new int[100002];
    static int groupSize[] = new int[100002];
    static int counters[] = new int[100002];
    static int n;

    static int min(int a, int b) {
        if (a < b) {
            return a;
        } else {
            return b;
        }
    }

    static StreamTokenizer in;
    static PrintWriter out;

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

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

        n = nextInt();

        for (int i = 0; i < n - 1; i++) {
            masa[i] = nextInt();
            masb[i] = nextInt();

            degree[masa[i]]++;
            degree[masb[i]]++;

            neighboursum[masa[i]] += masb[i];
            neighboursum[masb[i]] += masa[i];
        }

        int prieksa = 0;
        int aste = 0;

        for (int i = 1; i <= n; i++) {
            subtree[i] = 1;
            place[i] = i;

            if (degree[i] == 1) {
                rinda[prieksa] = i;
                prieksa++;
            }
        }

        while (prieksa > aste) {

            int x = rinda[aste];
            aste++;

            int y = (int) neighboursum[x];

            if (y > 0) {
                if (fatchild[y] == 0 || subtree[fatchild[y]] < subtree[x]) {
                    fatchild[y] = x;
                }

                subtree[y] += subtree[x];

                degree[y]--;
                neighboursum[y] -= x;

                if (degree[y] == 1) {
                    rinda[prieksa] = y;
                    prieksa++;
                }
            }
        }

        long minDistance = 0;
        long maxDistance = 0;

        for (int i = 0; i < n; i++) {
            int x = rinda[i];

            if (place[x] == x) {
                int y = (int) neighboursum[x];

                if (y > 0) {
                    place[x] = place[y];
                    place[y] = x;
                    minDistance += 2;
                } else {

                    int j = i;
                    int z;

                    do {
                        j--;
                        z = rinda[j];
                    } while (j >= 0 && neighboursum[z] != x);

                    place[x] = place[z];
                    place[z] = x;

                    minDistance += 2;
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            maxDistance += 2 * min(subtree[i], n - subtree[i]);
        }

        out.print(minDistance);
        out.print(" ");
        out.println(maxDistance);

        for (int i = 1; i <= n; i++) {
            out.print(place[i]);

            if (i < n) {
                out.print(" ");
            } else {
                out.println();
            }
        }

        // find centroid
        int c = 1;
        int cc = 1;

        do {
            c = cc;

            if (subtree[c] < n / 2 + n % 2) {
                cc = (int) neighboursum[c];
            } else if (subtree[c] > n / 2) {
                if (fatchild[c] != 0 && subtree[fatchild[c]] > n / 2) {
                    cc = fatchild[c];
                }
            }
        } while (cc != c);

        int nextGroup = 2;

        for (int i = n - 1; i >= 0; i--) {
            int x = rinda[i];

            if ((x == c) || (neighboursum[x] == c)) {
                group[x] = nextGroup;
                nextGroup++;
            } else if (neighboursum[x] > 0) {
                group[x] = group[(int) neighboursum[x]];
            } else {
                group[x] = 1;
            }

            groupSize[group[x]]++;
        }

        for (int i = 1; i < nextGroup; i++) {
            groupSize[i] += groupSize[i - 1];
        }

        for (int i = 1; i <= n; i++) {
            order[groupSize[group[i] - 1] + counters[group[i]]] = i;
            counters[group[i]]++;
        }

        for (int i = 0; i < n; i++) {
            place2[order[i]] = order[(i + n / 2) % n];
        }

        for (int i = 1; i <= n; i++) {
            out.print(place2[i]);

            if (i < n) {
                out.print(" ");
            } else {
                out.println();
            }
        }

        out.flush();
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 38 / 38
• Subtask 3: 50 / 50