Submission #687829

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
687829	2023-01-27T02:10:14 Z	2vas	Sailing Race (CEOI12_race)	C++17	40 / 100	344 ms	6612 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	0 ms	212 KB	Output isn't correct
3	Incorrect	1 ms	212 KB	Output isn't correct
4	Incorrect	1 ms	340 KB	Output isn't correct
5	Correct	1 ms	340 KB	Output is correct
6	Incorrect	1 ms	340 KB	Output isn't correct
7	Correct	4 ms	724 KB	Output is correct
8	Incorrect	2 ms	340 KB	Output isn't correct
9	Correct	5 ms	596 KB	Output is correct
10	Correct	15 ms	1236 KB	Output is correct
11	Correct	8 ms	820 KB	Output is correct
12	Incorrect	23 ms	1244 KB	Output isn't correct
13	Incorrect	37 ms	1748 KB	Output isn't correct
14	Correct	64 ms	2496 KB	Output is correct
15	Incorrect	208 ms	4948 KB	Output isn't correct
16	Incorrect	295 ms	5764 KB	Output isn't correct
17	Incorrect	228 ms	4956 KB	Output isn't correct
18	Correct	83 ms	3156 KB	Output is correct
19	Incorrect	343 ms	6560 KB	Output isn't correct
20	Incorrect	344 ms	6612 KB	Output isn't correct