oj.uz

Submission #687824

# Submission time Handle Problem Language Result Execution time Memory
687824 2023-01-27T02:04:54 Z 2vas Sailing Race (CEOI12_race) C++17
0 / 100
 387 ms 8528 KB 
#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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Incorrect 1 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 Incorrect 1 ms 340 KB Output isn't correct
6 Incorrect 2 ms 448 KB Output isn't correct
7 Incorrect 4 ms 596 KB Output isn't correct
8 Incorrect 3 ms 468 KB Output isn't correct
9 Incorrect 6 ms 724 KB Output isn't correct
10 Incorrect 16 ms 1364 KB Output isn't correct
11 Incorrect 9 ms 852 KB Output isn't correct
12 Incorrect 24 ms 1388 KB Output isn't correct
13 Incorrect 46 ms 2168 KB Output isn't correct
14 Incorrect 77 ms 3440 KB Output isn't correct
15 Incorrect 259 ms 6720 KB Output isn't correct
16 Incorrect 291 ms 7568 KB Output isn't correct
17 Incorrect 235 ms 6716 KB Output isn't correct
18 Incorrect 106 ms 4680 KB Output isn't correct
19 Incorrect 372 ms 8528 KB Output isn't correct
20 Incorrect 387 ms 8388 KB Output isn't correct