Submission #63292

#	Time	Username	Problem	Language	Result	Execution time	Memory
63292		evpipis	Jousting tournament (IOI12_tournament)	C++11	0 / 100	34 ms	7608 KiB

tournament

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

//#define TEST

#ifdef TEST
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
#endif // TEST

#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

const int len = 2e5+5;
vector<int> adj[len];
int nex[len], nod[len], fir[len], out[len];
ii inter[len];

ii dfs(int u){
    if (adj[u].size() == 0) return mp(0, u);

    ii ans = mp(-1, -1);
    int temp = (fir[inter[u].fi] >= inter[u].se);
    for (int j = 0; j < adj[u].size(); j++){
        int v = adj[u][j];
        out[v] = out[u]+temp;
        ii cur = dfs(v);

        if (cur.fi > ans.fi)
            ans = cur;
        else if (cur.fi == ans.fi && cur.se < ans.se)
            ans = cur;
    }

    ans.fi += temp;
    return ans;
}

int GetBestPosition(int n, int q, int p, int *arr, int *st, int *en){
    int m = n-1;
    for (int i = 0; i < n; i++){
        nex[i] = i+1;
        nod[i] = i;
    }

    for (int i = 0; i < q; i++){
        int pos = st[i], rem = en[i]-st[i];

        ++m;
        while (rem--){
            adj[m].pb(nod[pos]);
            pos = nex[pos];
        }
        adj[m].pb(nod[pos]);

        nex[st[i]] = nex[pos];
        nod[st[i]] = m;
        inter[m] = mp(st[i], nex[pos]-1);
    }

    /*for (int i = 0; i <= m; i++){
        printf("%d(%d, %d):", i, inter[i].fi, inter[i].se);
        for (int j = 0; j < adj[i].size(); j++)
            printf(" %d", adj[i][j]);
        printf("\n");
    }*/

    arr[n-1] = n;
    for (int i = 0, j = 0; i < n; i++){
        j = max(j, i);
        while (arr[j] <= p)
            j++;

        fir[i] = j;
        //printf("i = %d, j = %d\n", i, j);
    }

    //printf("%d, %d\n", dfs(m).fi, dfs(m).se);
    ii temp = dfs(m);
    ii ans = mp(-1, -1);
    for (int i = 0; i < n; i++)
        if (out[i] > ans.fi || (out[i] == ans.fi && i < ans.se))
            ans = mp(out[i], i);

    //for (int i = 0; i < n; i++)
      //  printf("%d ", out[i]);
    //printf("\n");
    return ans.se;
}

#ifdef TEST
int main() {
  //freopen("example.txt", "r", stdin);
  int tmp;

  /* Set input and output buffering */
  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  assert(tmp == 0);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
  assert(tmp == 0);

  int N, C, R;
  int *K, *S, *E;
  tmp = scanf("%d %d %d", &N, &C, &R);
  assert(tmp == 3);
  K = (int*) malloc((N-1) * sizeof(int));
  S = (int*) malloc(C * sizeof(int));
  E = (int*) malloc(C * sizeof(int));
  int i;
  for (i = 0; i < N-1; i++) {
    tmp = scanf("%d", &K[i]);
    assert(tmp == 1);
  }
  for (i = 0; i < C; i++) {
    tmp = scanf("%d %d", &S[i], &E[i]);
    assert(tmp == 2);
  }

  printf("%d\n", GetBestPosition(N, C, R, K, S, E));

  return 0;

}
#endif // TEST

/*
8 5 3
0 1 2 4 5 6 7
6 7
4 5
1 3
0 2
0 1

5 4 2
0 1 3 4
0 1
0 1
0 1
0 1
*/

Compilation message (stderr)

tournament.cpp: In function 'ii dfs(int)':
tournament.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:83:8: warning: variable 'temp' set but not used [-Wunused-but-set-variable]
     ii temp = dfs(m);
        ^~~~

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