Submission #528168

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
528168	2022-02-19T14:46:57 Z	zxcvbnm	Sailing Race (CEOI12_race)	C++14	10 / 100	19 ms	4936 KB

race

/*

7 1
5 0 2
5 0
7 0
3 0
4 0
4 3 0
2 1 0

*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int nax = 105;
vector<int> adj[nax];
int dp[nax][nax][nax];
int n, k;

#define watch(x) cerr << (#x) << ": " << x << "\n";

bool in(int l, int r, int x) {
    if (l <= r) {
        return x >= l && x <= r;
    }
    else {
        return x >= l || x <= r;
    }
}

int go(int l, int r, int s) {
//    cout << l+1 << " " << r+1 << " " << s+1 << ":\n";
//    for(int i : path) {
//        cout << i+1 << " ";
//    } cout << "\n";

    if (l == r) {
        return 0;
    }
    if (dp[l][r][s] != -1) {
        return dp[l][r][s];
    }

    int& ret = dp[l][r][s];
    ret = 0;
//    watch(s);

    for(int u : adj[s]) {
//        cout << u << "\n";
        if (!in(l, r, u)) continue;

        int L, R;

        // choice 1
        if (u != l) {
            L = l, R = (((u-1)%n)+n)%n;
            ret = max(ret, go(L, R, u)+1);
        }

        // choice 2
        if (u != r) {
            L = (u+1)%n, R = r;
            ret = max(ret, go(L, R, u)+1);
        }
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    assert(k == 0);
    assert(n <= 105);
    for(int i = 0; i < n; i++) {
        int x;
        while(1) {
            cin >> x;
            if (x == 0) break;
//            cout << i << "->" << x << "\n";
            x--;
            adj[i].push_back(x);
        }
    }

    memset(dp, -1, sizeof dp);
    int mx = -1;
    int idx = 0;
    for(int i = 0; i < n; i++) {
        int curr = go((i+1)%n, (((i-1)%n)+n)%n, i);
        if (curr > mx) {
            mx = curr;
            idx = i;
        }
    }
    cout << mx << "\n";
    cout << idx+1 << "\n";
    return 0;
}

/*

7 0
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0

*/

Subtask #1

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4812 KB	Output is correct
2	Runtime error	1 ms	452 KB	Execution killed with signal 6
3	Runtime error	1 ms	460 KB	Execution killed with signal 6
4	Runtime error	1 ms	448 KB	Execution killed with signal 6
5	Incorrect	3 ms	4812 KB	Output isn't correct
6	Runtime error	1 ms	460 KB	Execution killed with signal 6
7	Incorrect	8 ms	4880 KB	Output isn't correct
8	Runtime error	1 ms	460 KB	Execution killed with signal 6
9	Correct	8 ms	4804 KB	Output is correct
10	Incorrect	19 ms	4936 KB	Output isn't correct
11	Incorrect	11 ms	4812 KB	Output isn't correct
12	Runtime error	1 ms	460 KB	Execution killed with signal 6
13	Runtime error	1 ms	460 KB	Execution killed with signal 6
14	Runtime error	1 ms	460 KB	Execution killed with signal 6
15	Runtime error	1 ms	456 KB	Execution killed with signal 6
16	Runtime error	1 ms	464 KB	Execution killed with signal 6
17	Runtime error	1 ms	460 KB	Execution killed with signal 6
18	Runtime error	2 ms	520 KB	Execution killed with signal 6
19	Runtime error	2 ms	456 KB	Execution killed with signal 6
20	Runtime error	1 ms	460 KB	Execution killed with signal 6