답안 #328812

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
328812 2020-11-18T06:42:54 Z thecodingwizard Sailing Race (CEOI12_race) C++11
40 / 100
178 ms 9964 KB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010

#define maxn 500
int n, k; 
vector<int> adj[maxn];
vector<int> radj[maxn];

int memo[maxn][maxn][2];
int dp(int x, int y, bool onY) {
    if (memo[x][y][onY] != -1) return memo[x][y][onY];
    int best = 1;

    for (int i : adj[onY ? y : x]) {
        bool legal = false;
        if (x < y) {
            if (x < i && i < y) {
                legal = true;
            }
        } else {
            if (i > x || i < y) {
                legal = true;
            }
        }
        if (!legal) continue;

        best = max(best, 1 + max(dp(x, i, 1), dp(i, y, 0)));
    }

    return memo[x][y][onY] = best;
}

// path[i][x] = longest path to x starting from i, going counterclockwise
int path[maxn][maxn];
// going clockwise
int pathRev[maxn][maxn];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> k;
    F0R(i, n) {
        int x;
        while (cin >> x && x != 0) {
            --x;
            adj[i].pb(x);
            radj[x].pb(i);
        }
    }

    int best = -1, bestIdx = -1;

    F0R(i, n) F0R(j, n) F0R(k, 2) memo[i][j][k] = -1;

    F0R(i, n) {
        path[i][i] = pathRev[i][i] = 1;
    }

    F0R(i, n) {
        for (int j : adj[i]) {
            int val = max(dp(i, j, 1), dp(j, i, 0));
            if (best < val) {
                best = val;
                bestIdx = i;
            }
        }
        if (k) {
            sort(all(radj[i]), [&i](int x, int y){return (i-x+n)%n-(i-y+n)%n;});

            int add = 0;
            for (int j : radj[i]) {
                //while (add < n && ((i < j && (i+add)%n < j) || (i > j && ((i+add)%n > i || (i+add)%n < j)))) {
                while (add < (j-i+n)%n) {
                    int cur = (i+add)%n;
                    add++;
                    if (path[i][cur] == 0) continue;
                    for (int nxt : adj[cur]) {
                        if ((cur >= i && (nxt > cur || nxt < i)) || (cur <= i && (cur < nxt && nxt < i))) {
                            path[i][nxt] = max(path[i][nxt], path[i][cur]+1);
                        }
                    }
                }
                F0R(add, n) {
                    int tmp = i;
                    int i = j; int j = tmp;
                    int cur = (i+add)%n;
                    int newVal = -1;
                    int newVal2 = -1;

                    if ((j > i && (i < cur && cur < j)) || (j < i && (cur > i || cur < j))) {
                        newVal = path[j][cur] + max(dp(cur, j, 0), dp(i, cur, 1)) - 1;
                    } else if (cur != i && cur != j) {
                        newVal2 = pathRev[j][cur] + max(dp(j, cur, 1), dp(cur, i, 0)) - 1;
                    }

                    int val = max(newVal, newVal2);
                    if (best < val) {
                        best = val;
                        bestIdx = i;
                    }
                }
            }

            reverse(all(radj[i]));
            int sub = 0;
            for (int j : radj[i]) {
                while (sub < (i-j+n)%n) {
                    int cur = (i-sub+n)%n;
                    //cout << j << "-->" << i << ": processed " << cur << endl;
                    sub++;
                    if (pathRev[i][cur] == 0) continue;
                    for (int nxt : adj[cur]) {
                        if ((cur >= i && (i < nxt && nxt < cur)) || (cur <= i && (nxt > i || nxt < cur))) {
                            pathRev[i][nxt] = max(pathRev[i][nxt], pathRev[i][cur]+1);
                        }
                    }
                }
                F0R(add, n) {
                    int tmp = i;
                    int i = j; int j = tmp;
                    int cur = (i+add)%n;
                    int newVal = -1;
                    int newVal2 = -1;

                    if ((j > i && (i < cur && cur < j)) || (j < i && (cur > i || cur < j))) {
                        newVal = path[j][cur] + max(dp(cur, j, 0), dp(i, cur, 1)) - 1;
                    } else if (cur != i && cur != j) {
                        newVal2 = pathRev[j][cur] + max(dp(j, cur, 1), dp(cur, i, 0)) - 1;
                    }

                    int val = max(newVal, newVal2);
                    if (best < val) {
                        best = val;
                        bestIdx = i;
                    }
                }
            }
        }
    }

    cout << best << endl;
    cout << bestIdx+1 << endl;

    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Incorrect 1 ms 492 KB Output isn't correct
3 Incorrect 1 ms 620 KB Output isn't correct
4 Incorrect 2 ms 748 KB Output isn't correct
5 Correct 1 ms 748 KB Output is correct
6 Runtime error 4 ms 1644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Correct 5 ms 1004 KB Output is correct
8 Runtime error 4 ms 1900 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Correct 6 ms 1132 KB Output is correct
10 Correct 18 ms 1260 KB Output is correct
11 Correct 9 ms 1260 KB Output is correct
12 Runtime error 28 ms 3948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 20 ms 5484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 69 ms 3820 KB Output is correct
15 Runtime error 104 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 138 ms 9964 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 118 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Correct 86 ms 4460 KB Output is correct
19 Runtime error 178 ms 9836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 162 ms 9836 KB Execution killed with signal 11 (could be triggered by violating memory limits)