oj.uz

Submission #146458

# Submission time Handle Problem Language Result Execution time Memory
146458 2019-08-24T07:51:36 Z dolphingarlic Jousting tournament (IOI12_tournament) C++14
100 / 100
 113 ms 19988 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 7 ms 5116 KB Output is correct
7 Correct 7 ms 5240 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 7 ms 5112 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 10 ms 5880 KB Output is correct
3 Correct 8 ms 5240 KB Output is correct
4 Correct 11 ms 5544 KB Output is correct
5 Correct 10 ms 5496 KB Output is correct
6 Correct 10 ms 5368 KB Output is correct
7 Correct 11 ms 5624 KB Output is correct
8 Correct 10 ms 5624 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 12 ms 5496 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 8640 KB Output is correct
2 Correct 104 ms 19988 KB Output is correct
3 Correct 51 ms 9336 KB Output is correct
4 Correct 101 ms 16724 KB Output is correct
5 Correct 101 ms 17532 KB Output is correct
6 Correct 113 ms 12152 KB Output is correct
7 Correct 103 ms 17824 KB Output is correct
8 Correct 103 ms 17656 KB Output is correct
9 Correct 45 ms 8816 KB Output is correct
10 Correct 57 ms 9156 KB Output is correct