Submission #528168

#	Time	Username	Problem	Language	Result	Execution time	Memory
528168		zxcvbnm	Sailing Race (CEOI12_race)	C++14	10 / 100	19 ms	4936 KiB

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 / 100