437.java

import java.io.OutputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.TreeSet;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Artem Gilmudinov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream;
        try {
            inputStream = new FileInputStream("input.txt");
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        OutputStream outputStream;
        try {
            outputStream = new FileOutputStream("output.txt");
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskAcmpFast solver = new TaskAcmpFast();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskAcmpFast {
        private static final int[] EMPTY = new int[0];

        public void e(boolean flag) {
            if (!flag) {
                throw new RuntimeException();
            }
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int k, n, m;
            k = in.readInt();
            n = in.readInt();
            m = in.readInt();
            long[] u = new long[n];
            long[] v = new long[n];
            for (int i = 0; i < n; i++) {
                u[i] = in.readLong() - 1;
                v[i] = in.readLong() - 1;
            }
            long[] players = new long[m];
            for (int i = 0; i < m; i++) {
                players[i] = in.readLong() - 1;
            }
            Arrays.sort(players);
            TreeSet<Long> present = new TreeSet<>();

            for (long p : players) {
                present.add(p);
            }
            for (long p : u) {
                present.add(p);
            }
            for (long p : v) {
                present.add(p);
            }

            //массив уникальных игроков. в дальнейшем мы будем обращаться к ним по индексу этого массива вместо большого номера
            long[] unique = new long[present.size()];
            int len = unique.length;
            int cur = 0;
            for (long val : present) {
                unique[cur++] = val;
            }
            present.clear();

            //cntWin[i] - количество участников которых выигрывает i игрок
            int[] cntWin = new int[len];

            //cntLose[i] - количество участников которым проигрывает i игрок
            int[] cntLose = new int[len];

            for (int i = 0; i < n; i++) {
                cntWin[Arrays.binarySearch(unique, u[i])]++;
                cntLose[Arrays.binarySearch(unique, v[i])]++;
            }

            //win[i] - массив тех кого выигрывает i
            int[][] win = new int[len][];

            //lose[i] - массив тех кому проигрывает i
            int[][] lose = new int[len][];
            for (int i = 0; i < len; i++) {
                if (cntWin[i] == 0) {
                    win[i] = EMPTY;
                } else {
                    win[i] = new int[cntWin[i]];
                }
                if (cntLose[i] == 0) {
                    lose[i] = EMPTY;
                } else {
                    lose[i] = new int[cntLose[i]];
                }
            }

            int pos1, pos2;
            for (int i = 0; i < n; i++) {
                pos1 = Arrays.binarySearch(unique, u[i]);
                pos2 = Arrays.binarySearch(unique, v[i]);
                win[pos1][--cntWin[pos1]] = pos2;
                lose[pos2][--cntLose[pos2]] = pos1;
            }

            //проверяем что все рёбра были выставлены
            for (int i = 0; i < len; i++) {
                e(cntWin[i] == 0 && cntLose[i] == 0);
            }
            u = v = null;
            cntWin = cntLose = null;

            boolean isOk, whichHalf; //true - left, false - right

            long group, val1, val2, from, to, mid, fromSub, toSub;
            int leftCnt, rightCnt, cnt, leftCntWin, rightCntWin;

            byte[] dp = new byte[len]; //dp[i] - в каком максимальном туре может выиграть i-ый игрок
            for (int i = 1; i <= k; i++) {

                long d = (1l << i); //количество игроков в группе на i-ом уровне

                for (int j = 0, z = 0; j < len; ) {
                    group = unique[j] / d; //номер текущей группы
                    from = group * d; //начало текущей группы
                    to = group * d + d - 1; //конец текущей группы
                    mid = (to + from) / 2; //середина текущей группы
                    leftCnt = rightCnt = 0; // количество игроков в левой и правой половине, которые есть во вход. данных
                    leftCntWin = rightCntWin = 0; //количество игроков в левой и правой половине,
                    // которые есть во вход.данных и могут дойти до i тура

                    //находим участников которые в текущей группе
                    for (; z < len; z++) {
                        if (group != unique[z] / d) {
                            break;
                        }
                        if (unique[z] <= mid) {
                            leftCnt++;
                            if (dp[z] == i - 1) {
                                leftCntWin++;
                            }
                        } else {
                            rightCnt++;
                            if (dp[z] == i - 1) {
                                rightCntWin++;
                            }
                        }
                    }

                    //пересчитываем dp для каждого игрока группы
                    for (int p = j; p < z; p++) {
                        //если не можем дойти до i тура то выходим, ибо улучшить нельзя
                        if (dp[p] != i - 1) {
                            continue;
                        }

                        val1 = unique[p];

                        //выясняем в какой половине лежит текущий игрок, и задаём границы противополжной половины
                        if (val1 <= mid) {
                            fromSub = mid + 1;
                            whichHalf = true;
                            toSub = to;
                        } else {
                            fromSub = from;
                            whichHalf = false;
                            toSub = mid;
                        }
                        //если есть в противоположной половине игрок, который не присутствует во входных данных, то p-й игрок
                        //может выиграть
                        isOk = (whichHalf && rightCnt < d / 2) || (!whichHalf && leftCnt < d / 2);
                        //иначе проверяем есть ли в противополжной половине игрок, которого мы можем выиграть по договору
                        //и он может дойти до i тура
                        if (!isOk) {
                            for (int t : win[p]) {
                                val2 = unique[t];
                                if (dp[t] >= i - 1 && val2 >= fromSub && val2 <= toSub) {
                                    isOk = true;
                                    break;
                                }
                            }
                        }
                        //иначе проверяем есть ли в противоположной половине такой игрок, с которым у p нет договорного матча
                        // и он может дойти до i тура
                        if (!isOk) {
                            cnt = 0;
                            //считаем количество игроков из противоположной половины которым p проигрывает и
                            // которые могут дойти до i
                            for (int t : lose[p]) {
                                val2 = unique[t];
                                if (dp[t] >= i - 1 && val2 >= fromSub && val2 <= toSub) {
                                    cnt++;
                                }
                            }
                            //если их количество меньше чем количество игроков в против. половине которые могут дойти до i
                            // то есть игрок с которым нет договора
                            if ((whichHalf && cnt != rightCntWin) || (!whichHalf && cnt != leftCntWin)) {
                                isOk = true;
                            }

                            //проверяем что таких  меньше чем всего количество способных дойти до i
                            if (whichHalf) {
                                e(cnt <= rightCntWin);
                            } else {
                                e(cnt <= leftCntWin);
                            }
                        }
                        //если одно из условий удовлетворено, то обновляем dp[p]
                        if (isOk) {
                            dp[p] = (byte) i;
                        }
                    }

                    j = z;
                }

            }
            //выводим ответ
            int printed = 0;
            for (int i = 0, j = 0; i < m; i++) {
                for (; j < len; j++) {
                    if (unique[j] == players[i]) {
                        if (dp[j] == k) {
                            out.print(k + " ");
                        } else {
                            out.print((dp[j] + 1) + " ");
                        }
                        printed++;
                        break;
                    }
                }
            }

            //проверяем что все выведены
            e(printed == m);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long readLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}

Перебираем туры, пусть текущий тур i, и для каждого игрока v считаем следующее значение win[v] - какой максимальный тур v может выиграть.
Пересчитываем win[v] для i + 1 так:
a) если есть игрок в противополжной половине, которого нету во входных данных, то win[v] = i + 1.
b) иначе если есть игрок в противополжной половине, который может дойти до i + 1 и которого v может выиграть по договору, то win[v] = i + 1.
c) иначе если есть игрок в противополжной половине, который может дойти до i + 1 и с которым у v нет договорного матча, то win[v] = i + 1.
d) иначе win[v] остаётся неизменным.
Решение проходит на informatics.mccme.ru все тесты, за исключением 4-х (WA). Причём эти 4 теста маленькие (судя по времени работы), а большие проходит.
Что я мог забыть?