Submission #102685

#	Time	Username	Problem	Language	Result	Execution time	Memory
102685		popovicirobert	Jousting tournament (IOI12_tournament)	C++14	100 / 100	227 ms	42284 KiB

tournament

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))

using namespace std;

typedef vector <int> VI;
typedef vector <VI> VVI;

struct Fenwick {
    VI aib;
    int n;
    inline void init(int _n) {
        n = _n;
        aib.resize(n + 1);
    }
    inline void clr() {
        fill(aib.begin(), aib.end(), 0);
    }
    inline void update(int pos, int val) {
        for(int i = pos; i <= n; i += lsb(i)) {
            aib[i] += val;
        }
    }
    inline int query(int pos) {
        int ans = 0;
        for(int i = pos; i > 0; i -= lsb(i)) {
            ans += aib[i];
        }
        return ans;
    }
    inline int sum(int l, int r) {
        return query(r) - query(l - 1);
    }
    inline int kth(int k) {
        int res = 0, cnt = 0;
        for(int step = 1 << 17; step; step >>= 1) {
            if(res + step <= n && cnt + aib[res + step] < k) {
                res += step;
                cnt += aib[res];
            }
        }
        return res + 1;
    }
};

void dfs(int nod, VVI &g, VI &idl, VI &idr, VI &lvl, int n) {
    idl[nod] = n + 1, idr[nod] = 0;
    for(auto it : g[nod]) {
        lvl[it] = lvl[nod] + 1;
        dfs(it, g, idl, idr, lvl, n);
        idl[nod] = min(idl[nod], idl[it]), idr[nod] = max(idr[nod], idr[it]);
    }
    if(nod <= n) {
        idl[nod] = idr[nod] = nod;
    }
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    Fenwick fen; fen.init(N);
    for(int i = 1; i <= N; i++) {
        fen.update(i, 1);
    }

    VVI g(N + C + 1); VI id(N + 1);
    iota(id.begin(), id.end(), 0);
    VVI anc(N + C + 1, VI(18));

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

        int aux = fen.kth(S[i]);
        for(int j = S[i]; j <= E[i]; j++) {
            int pos = fen.kth(S[i]);
            fen.update(pos, -1);

            g[cur].push_back(id[pos]);
            anc[id[pos]][0] = cur;

        }
        fen.update(aux, 1);
        id[aux] = cur;
    }

    for(int bit = 1; bit <= 17; bit++) {
        for(int i = 1; i <= cur; i++) {
            anc[i][bit] = anc[anc[i][bit - 1]][bit - 1];
        }
    }

    VI idl(cur + 1), idr(cur + 1), lvl(cur + 1);

    for(int i = cur; i >= 1; i--) {
        if(lvl[i] == 0) {
            dfs(i, g, idl, idr, lvl, N);
        }
    }

    fen.clr();
    for(int i = 2; i <= N; i++) {
        fen.update(i, (K[i - 2] > R));
    }

    int ans, mx = -1;
    for(int i = 1; i <= N; i++) {
        int nod = i;
        for(int bit = 17; bit >= 0; bit--) {
            int cur = anc[nod][bit];
            if(cur > 0 && fen.sum(idl[cur], idr[cur]) == 0) {
                nod = cur;
            }
        }

        if(mx < lvl[i] - lvl[nod]) {
            mx = lvl[i] - lvl[nod], ans = i;
        }

        if(i < N) {
            if(K[i - 1] > R) {
                fen.update(i + 1, -1);
                fen.update(i, 1);
            }
        }
    }
    return ans - 1;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:125:18: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ans - 1;
                  ^

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