Submission #146458

#	Time	Username	Problem	Language	Result	Execution time	Memory
146458		dolphingarlic	Jousting tournament (IOI12_tournament)	C++14	100 / 100	113 ms	19988 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

int bit[100001], nodeat[100001];

void update(int pos, int val, int N) {
    for (; pos <= N; pos += (pos & (-pos))) bit[pos] += val;
}
int query(int pos, int N) {
    int ans = 0;
    for (; pos > 0; pos -= (pos & (-pos))) ans += bit[pos];
    return ans;
}
int binsearch(int val, int N) {
    int l = 1, r = N;
    while (l != r) {
        int mid = (l + r) / 2;
        if (query(mid, N) < val)
            l = mid + 1;
        else
            r = mid;
    }
    return l;
}

vector<int> graph[200001];
int colour[200001], knights[100001];
pair<int, int> maxwins[200001];

int ans_wins = 0, ans_node = 1;

// 0 = All W, 1 = Leftmost B; everthing else W, 2 = B somewhere else
void dfs(int node) {
    if (graph[node].empty()) {
        colour[node] = knights[node];
        maxwins[node] = {0, node};
    } else {
        for (int i : graph[node]) {
            dfs(i);
            if (colour[i] && i != graph[node].back()) colour[node] = 2;
        }
        if (colour[node] != 2) {
            if (colour[graph[node].back()])
                colour[node] = 1;
            else
                colour[node] = 0;
        }

        if (colour[node] < 2) {
            int wins = 0, best = 1;
            for (int i : graph[node]) {
                if (maxwins[i].first + 1 >= wins)
                    wins = maxwins[i].first + 1, best = maxwins[i].second;
            }
            maxwins[node] = {wins, best};
        } else
            maxwins[node] = maxwins[graph[node].back()];
    }

    if (maxwins[node].first > ans_wins)
        ans_wins = maxwins[node].first, ans_node = maxwins[node].second;
    else if (maxwins[node].first == ans_wins)
        ans_node = min(ans_node, maxwins[node].second);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    for (int i = 1; i <= N; i++) {
        update(i, 1, N);
        nodeat[i] = i;
    }

    int indx = N;
    for (int i = 0; i < C; i++) {
        S[i]++, E[i]++;
        indx++;

        for (int j = E[i]; j > S[i]; j--) {
            int pos = binsearch(j, N);
            graph[indx].push_back(nodeat[pos]);
            update(pos, -1, N);
        }
        int pos = binsearch(S[i], N);
        graph[indx].push_back(nodeat[pos]);
        nodeat[pos] = indx;
    }

    knights[1] = 0;
    for (int i = 0; i < N - 1; i++) knights[i + 2] = (K[i] > R);

    dfs(indx);

    return ans_node - 1;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51