Submission #687825

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
687825	2023-01-27T02:05:47 Z	2vas	Sailing Race (CEOI12_race)	C++17	15 / 100	355 ms	6560 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) {
    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

15.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	212 KB	Output isn't 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	2 ms	340 KB	Output isn't correct
7	Incorrect	4 ms	596 KB	Output isn't correct
8	Incorrect	2 ms	340 KB	Output isn't correct
9	Incorrect	5 ms	596 KB	Output isn't correct
10	Incorrect	19 ms	1236 KB	Output isn't correct
11	Incorrect	7 ms	820 KB	Output isn't correct
12	Incorrect	20 ms	1236 KB	Output isn't correct
13	Incorrect	33 ms	1748 KB	Output isn't correct
14	Correct	59 ms	2496 KB	Output is correct
15	Incorrect	216 ms	4948 KB	Output isn't correct
16	Incorrect	273 ms	5756 KB	Output isn't correct
17	Incorrect	190 ms	4948 KB	Output isn't correct
18	Correct	82 ms	3212 KB	Output is correct
19	Incorrect	355 ms	6560 KB	Output isn't correct
20	Incorrect	344 ms	6548 KB	Output isn't correct