Submission #687829

#	Time	Username	Problem	Language	Result	Execution time	Memory
687829		2vas	Sailing Race (CEOI12_race)	C++17	40 / 100	344 ms	6612 KiB

race

#include <bits/stdc++.h>
using namespace std;

void solve();

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t=1; // cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

int n;
bool inOrder(int a, int b, int c) {
    if (a == b || b == c || c == a) return false;
    int d1 = b - a;
    if (d1 < 0) d1 += n;
    int d2 = c - a;
    if (d2 < 0) d2 += n;
    return d2 > d1;
}

void solve() {    
    int k; cin >> n >> k;

    set<int> edges[n];
    set<int> reversed_edges[n];
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        while (x != 0) {
            x--;
            edges[i].insert(x);
            reversed_edges[x].insert(i);
            // cout << i << ' ' << x << endl;
            cin >> x;
        }
    }

    // dp[prev][cur][1 if prev->cur, 0 if cur->prev]
    // is the length of longest not including prev -> cur
    int dp[n][n][2];
    memset(dp, 0, sizeof(dp));

    pair<int, int> best = make_pair(0,0);
    int bestBit = 0;
    for (int j = 1; j < n; j++) {
        // j is the distance between the two relavent nodes
        for (int i = 0; i < n; i++) {
            // compute dp[i][i+j][1] and dp[i+j][i][0]
            int k = i + j;
            if (k >= n) { k -= n; }
            
            // dp[i][k][1]
            for (int v : edges[k]) {
                if (!inOrder(i, v, k)) continue;

                dp[i][k][1] = max(dp[i][k][1], 1 + dp[k][v][0] );
                dp[i][k][1] = max(dp[i][k][1], 1 + dp[i][v][1] );
            }

            if (dp[best.first][best.second][bestBit] < dp[i][k][1] && edges[i].find(k) != edges[i].end()) {
                best = make_pair(i, k);
                bestBit = 1;
            }
            
            // dp[k][i][0]
            for (int v : edges[i]) {
                if (!inOrder(i, v, k)) continue;
                
                dp[k][i][0] = max(dp[k][i][0], 1 + dp[k][v][0]);
                dp[k][i][0] = max(dp[k][i][0], 1 + dp[i][v][1]);
            }
            

            if (dp[best.first][best.second][bestBit] < dp[k][i][0] && edges[k].find(i) != edges[k].end()) {
                best = make_pair(k, i);
                bestBit = 0;
            }
            
        }
    }

    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) {
    //         cout << dp[i][j][1] << ' ';
    //     }
    //     cout << endl;
    // }
    // cout << endl;

    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) {
    //         cout << dp[i][j][0] << ' ';
    //     }
    //     cout << endl;
    // }
    // cout << endl;

    cout << dp[best.first][best.second][bestBit] + 1 << endl;
    cout << best.first + 1 << endl;



}

• Subtask 1: 40 / 100