oj.uz

Submission #55256

# Submission time Handle Problem Language Result Execution time Memory
55256 2018-07-06T18:14:20 Z paulica Sailing Race (CEOI12_race) C++14
0 / 100
 3000 ms 8608 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 + 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 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 4 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 4 ms 1208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 6 ms 1516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 8 ms 1784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 11 ms 1984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 20 ms 2108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 21 ms 2380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 32 ms 2516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 41 ms 2636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 47 ms 2708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 253 ms 4428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 770 ms 6220 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 1840 ms 7832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Execution timed out 3028 ms 8608 KB Time limit exceeded
16 Execution timed out 3053 ms 8608 KB Time limit exceeded
17 Execution timed out 3072 ms 8608 KB Time limit exceeded
18 Execution timed out 3083 ms 8608 KB Time limit exceeded
19 Execution timed out 3053 ms 8608 KB Time limit exceeded
20 Execution timed out 3060 ms 8608 KB Time limit exceeded