제출 #63289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63289		evpipis	Jousting tournament (IOI12_tournament)	C++11	0 / 100	30 ms	8196 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];
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];
        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;
    }

    return dfs(m).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

컴파일 시 표준 에러 (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++){
                     ~~^~~~~~~~~~~~~~~

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