oj.uz

Submission #55257

# Submission time Handle Problem Language Result Execution time Memory
55257 2018-07-06T18:17:12 Z paulica Sailing Race (CEOI12_race) C++14
0 / 100
 2289 ms 9600 KB 
#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 == n - 1 ? 0 : i + 1;
    else return i == 0 ? n - 1 : i - 1;
    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);
        }

        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);
}

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}) {
                dpA(i, j, d);
                dpB(i, j, d);
            }

    assert(false);



    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);

    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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 3 ms 884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 4 ms 1192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 5 ms 1460 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 7 ms 1836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 8 ms 1976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 14 ms 2232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 14 ms 2360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 23 ms 2508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 34 ms 2644 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 29 ms 2732 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 108 ms 4360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 347 ms 6224 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 623 ms 7816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 1676 ms 9548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 2289 ms 9548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 1623 ms 9596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 1153 ms 9596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 2091 ms 9600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 1796 ms 9600 KB Execution killed with signal 11 (could be triggered by violating memory limits)