Submission #1096712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096712		vjudge1	Sailing Race (CEOI12_race)	C++17	60 / 100	415 ms	6636 KiB

race

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 500;
vector<vector<int>> a(MAXN, vector<int>(MAXN)), aa(MAXN, vector<int>(MAXN));
vector<vector<int>> md(MAXN, vector<int>(MAXN)), mdc(MAXN, vector<int>(MAXN));
vector<vector<int>> ed(MAXN, vector<int>(MAXN)), edc(MAXN, vector<int>(MAXN));
vector<vector<bool>> adj(MAXN, vector<bool>(MAXN));
vector<int> last(MAXN), b(MAXN), bb(MAXN);
int n, kk, max_val, maxi;
void inp() {
    cin >> n >> kk;
    for (int i = 0; i < n; i++) {
        int x;
        while (cin >> x && x > 0) {
            adj[i][x-1] = true;
        }
    }
    fill(b.begin(), b.end(), 0);
    fill(bb.begin(), bb.end(), 0);
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        while (i != j) {
            if (adj[i][j]) {
                b[i]++;
                a[i][b[i]] = j;
                md[i][j] = 1;
                mdc[i][j] = 1;
            }
            if (adj[j][i]) {
                bb[i]++;
                aa[i][bb[i]] = j;
            }
            j = (j + 1) % n;
        }
    }
}
void calc() {
    for (int i = 0; i < n; i++) {
        md[i][i] = mdc[i][i] = ed[i][i] = edc[i][i] = 0;
    }
    for (int t = 1; t < n; t++) {
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= b[i]; j++) {
                int y = a[i][j];
                int x = (i + t) % n;
                int h = (y + n - i) % n;
                if (h < t) {
                    if (md[y][x] > 0 && md[y][x] >= md[i][x])
                        md[i][x] = md[y][x] + 1;
                    if (ed[y][x] >= ed[i][x])
                        ed[i][x] = ed[y][x] + 1;
                    if (edc[y][i] >= ed[i][x])
                        ed[i][x] = edc[y][i] + 1;
                }
                x = (i + n - t) % n;
                h = (i + n - y) % n;
                if (h < t) {
                    if (mdc[y][x] > 0 && mdc[y][x] >= mdc[i][x])
                        mdc[i][x] = mdc[y][x] + 1;
                    if (edc[y][x] >= edc[i][x])
                        edc[i][x] = edc[y][x] + 1;
                    if (ed[y][i] >= edc[i][x])
                        edc[i][x] = ed[y][i] + 1;
                }
            }
        }
    }
    max_val = 0;
    for (int i = 0; i < n; i++) {
        if (edc[i][i] > max_val) {
            max_val = edc[i][i];
            maxi = i;
        }
        if (ed[i][i] > max_val) {
            max_val = ed[i][i];
            maxi = i;
        }
    }
}
void opt() {
    for (int i = 0; i < n; i++) {
        // case 1: i y z x 为正 positive
        for (int j = 2; j < n; j++) {
            int x = (i + j) % n;
            int k = 1;
            while (k <= bb[x] && (aa[x][k] + n - i - 1) % n > j - 1) k++;
            last[x] = (k <= bb[x]) ? aa[x][k] : -1;
        }
        for (int j = 2; j < n - 1; j++) {
            if (adj[i][(i + j) % n]) {
                int z = (i + j) % n;
                for (int k = j + 1; k < n; k++) {
                    int x = (i + k) % n;
                    if (last[x] > -1 && (n + last[x] - i) % n < j && md[x][i] > 0) {
                        int tmp = 1 + md[x][i] + 1 + max(edc[z][last[x]], ed[z][x]);
                        if (tmp > max_val) {
                            max_val = tmp;
                            maxi = last[x];
                        }
                    }
                }
            }
        }
        // case 2: i y z x 为负 negative
        for (int j = 1; j < n - 1; j++) {
            int x = (i + j) % n;
            int k = 1;
            while (k <= bb[x] && (aa[x][k] + n - i) % n > j) k++;
            last[x] = (k > 1) ? aa[x][k - 1] : -1;
        }
        for (int j = 2; j < n - 1; j++) {
            if (adj[i][(i + j) % n]) {
                int z = (i + j) % n;
                for (int k = 1; k < j; k++) {
                    int x = (i + k) % n;
                    if (last[x] > -1 && (n + last[x] - i) % n > j && mdc[x][i] > 0) {
                        int tmp = 1 + mdc[x][i] + 1 + max(ed[z][last[x]], edc[z][x]);
                        if (tmp > max_val) {
                            max_val = tmp;
                            maxi = last[x];
                        }
                    }
                }
            }
        }
    }
}
int main() {
    inp();
    calc();
    if (kk == 1) opt();
    cout << max_val << endl;
    cout << maxi + 1 << endl;
    return 0;
}

• Subtask 1: 60 / 100