답안 #55254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
55254	2018-07-06T18:08:59 Z	paulica	Sailing Race (CEOI12_race)	C++14	75 / 100	3000 ms	5056 KB

race

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

#define _ << " _ " <<
#define TRACE(x) cout << #x << " = " << x << endl

const int MaxN = 510;
int n, m;
int sol, start;

bool con[MaxN][MaxN];

int memoA[MaxN][MaxN][2], memoB[MaxN][MaxN][2];

int nxt(int i, int d) {
    if (d == 1) return (i + 1) % n;
    return (i - 1 + n) % n;
}

int dpA(int i, int j, int d) {
    int& dp = memoA[i][j][d];
    if (dp != -1) return dp;
    
    if (i == j) dp = 1;
    else if (con[i][j]) dp = 2;
    else dp = 0;

    for (int k = i; k != j; k = nxt(k, d))
        if (con[k][j] && dpA(i, k, d) > 0) dp = max(dp, dpA(i, k, d) + 1);

    return dp;
}

int dpB(int i, int j, int d) {
    int& dp = memoB[i][j][d];
    if (dp != -1) return dp;

    dp = (i != j);

    for (int k = i; k != j; k = nxt(k, d))
        if (con[i][k]) {
            dp = max(dp, dpB(k, j, d) + 1);
            dp = max(dp, dpB(k, i, 1 - d) + 1);
        }

    return dp;
}

void check(int cnt, int s) {
    if (cnt > sol) {
        sol = cnt;
        start = s;
    }
}

void solveS(int x, int s, int d) {
    int maxB = 0, t = -1;

    for (int i = nxt(s, d); i != x; i = nxt(i, d)) {
        if (con[s][i]) {
            t = i;
            check(dpA(t, x, d) + maxB, s);
//            TRACE(s _ t _ x _ i);
  //          TRACE(dpA(t, x, d) _ maxB);
         //   if (dpA(t, x, d) + maxB == 4) TRACE(s _ t _ x _ dpA(t, x, d) _ maxB);
      //      cout << endl;
        }

        if (con[x][i])
            maxB = max(maxB, dpB(i, s, 1 - d));
    }
}

void solveT(int x, int t, int d) {
    int maxB = 0, s = -1;
    
    for (int i = nxt(x, d); i != t; i = nxt(i, d))
        if (con[i][t]) {
            s = i;
            break;
        }

    if (s == -1) return;

    for (int i = nxt(s, d); i != t; i = nxt(i, d))
        if (con[x][i])
            maxB = max(maxB, dpB(i, t, d));

    check(dpA(t, x, d) + maxB, s);
    //TRACE(x _ t _ s _ d);
    //TRACE(dpA(t, x, d) _ maxB);
    //cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        int j;
        for (cin >> j; j != 0; cin >> j)
            con[i][j - 1] = true;

        for (int j = 0; j < n; j++)
            for (int d : {0, 1})
                memoA[i][j][d] = memoB[i][j][d] = -1;
    }

    /*
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int d : {0, 1})
                TRACE(i _ j _ d _ dpA(i, j, d));
                */

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int d : {0, 1})
                if (con[i][j]) check(dpB(j, i, d), i)/*, TRACE(i _ j _ d _ dpB(j, i, d))*/;

    if (m == 1)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (i != j) {
                    solveS(i, j, 0);
                    solveS(i, j, 1);
                    solveT(i, j, 0);
                    solveT(i, j, 1);
                }

    cout << sol << "\n" << start + 1 << "\n";

    return 0;
}

Subtask #1

75.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	612 KB	Output is correct
3	Correct	3 ms	704 KB	Output is correct
4	Correct	7 ms	720 KB	Output is correct
5	Correct	4 ms	880 KB	Output is correct
6	Correct	17 ms	948 KB	Output is correct
7	Correct	11 ms	1052 KB	Output is correct
8	Correct	31 ms	1204 KB	Output is correct
9	Correct	17 ms	1428 KB	Output is correct
10	Correct	21 ms	1572 KB	Output is correct
11	Correct	23 ms	1572 KB	Output is correct
12	Correct	498 ms	2404 KB	Output is correct
13	Correct	1472 ms	3300 KB	Output is correct
14	Correct	704 ms	4024 KB	Output is correct
15	Execution timed out	3074 ms	4964 KB	Time limit exceeded
16	Execution timed out	3061 ms	4964 KB	Time limit exceeded
17	Execution timed out	3058 ms	4964 KB	Time limit exceeded
18	Correct	1162 ms	5056 KB	Output is correct
19	Execution timed out	3034 ms	5056 KB	Time limit exceeded
20	Execution timed out	3065 ms	5056 KB	Time limit exceeded