oj.uz

Submission #143324

# Submission time Handle Problem Language Result Execution time Memory
143324 2019-08-13T16:17:29 Z popovicirobert Sailing Race (CEOI12_race) C++14
10 / 100
 3000 ms 2552 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long



/*const int MOD = ;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}

inline int inv(int x) {
    return lgput(x, MOD - 2);
}*/

/*int fact[], invfact[];

inline void prec(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    invfact[n] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--) {
        invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline int comb(int n, int k) {
    if(n < k) return 0;
    return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}*/

using namespace std;

const int INF = 1e9;
const int MAXN = 500;

int dp[MAXN][MAXN][2];
int best[MAXN];

int main() {
#if 0
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, j, n, k;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;
    vector < vector <int> > g(n);
    for(i = 0; i < n; i++) {
        int x;
        cin >> x;
        while(x != 0) {
            x--;
            g[i].push_back(x);
            cin >> x;
        }
    }

    for(int len = 1; len < n; len++) {
        for(i = 0; i + len < n; i++) {
            j = i + len;
            for(auto k : g[i]) {
                if(i < k && k < j) {
                    dp[i][j][0] = max(dp[i][j][0], 1 + max(dp[i][k][1], dp[k][j][0]));
                }
            }
            for(auto k : g[j]) {
                if(i < k && k < j) {
                    dp[i][j][1] = max(dp[i][j][1], 1 + max(dp[i][k][1], dp[k][j][0]));
                }
            }
        }
        for(j = 0; j + len < n; j++) { //i > j
            i = j + len;
            for(auto k : g[i]) {
                if(k < j || k > i) {
                    dp[i][j][0] = max(dp[i][j][0], 1 + max(dp[i][k][1], dp[k][j][0]));
                }
            }
            for(auto k : g[j]) {
                if(k < j || k > i) {
                    dp[i][j][1] = max(dp[i][j][1], 1 + max(dp[i][k][1], dp[k][j][0]));
                }
            }
        }
    }

    auto combine = [&](pair <int, int> &ans, pair <int, int> cur) {
        if(ans.first < cur.first) {
            swap(ans, cur);
        }
    };

    pair <int, int> ans = {0, 0};
    for(i = 0; i < n; i++) {
        for(auto j : g[i]) {
            combine(ans, {dp[i][j][1] + 1, i});
            combine(ans, {dp[j][i][0] + 1, i});
        }
    }
    if(k == 0) {
        cout << ans.first << "\n" << ans.second + 1;
        return 0;
    }

    auto prv = [&](int x) {
        return (x == 0 ? n - 1 : x - 1);
    };
    auto nxt = [&](int x) {
        return (x == n - 1 ? 0 : x + 1);
    };

    for(i = 0; i < n; i++) {
        for(auto j : g[i]) {
            fill(best, best + n, -INF);
            best[j] = 0;
            for(int k = j; k != i; k = nxt(k)) {
                for(auto it : g[k]) {
                    best[it] = max(best[it], best[k] + 1);
                }
                for(auto it : g[k]) {
                    if((i < j && i <= it && it <= j) || (i > j && (it >= i || it <= j))) continue;
                    combine(ans, {2 + best[k] + max(dp[it][j][0], dp[i][it][1]), i});
                }
            }

            fill(best, best + n, -INF);
            best[j] = 0;
            for(int k = j; k != i; k = prv(k)) {
                for(auto it : g[k]) {
                    best[it] = max(best[it], best[k] + 1);
                }
                for(auto it : g[k]) {
                    if((i < j && i <= it && it <= j) || (i > j && (it >= i || it <= j))) continue;
                    combine(ans, {2 + best[k] + max(dp[it][i][0], dp[j][it][1]), i});
                }
            }
        }
    }
    cout << ans.first << "\n" << ans.second + 1;


    return 0;
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Incorrect 3 ms 504 KB Output isn't correct
5 Incorrect 3 ms 504 KB Output isn't correct
6 Incorrect 8 ms 504 KB Output isn't correct
7 Incorrect 4 ms 632 KB Output isn't correct
8 Incorrect 9 ms 632 KB Output isn't correct
9 Incorrect 4 ms 760 KB Output isn't correct
10 Correct 8 ms 760 KB Output is correct
11 Incorrect 5 ms 760 KB Output isn't correct
12 Incorrect 266 ms 1208 KB Output isn't correct
13 Incorrect 403 ms 1656 KB Output isn't correct
14 Incorrect 37 ms 2016 KB Output isn't correct
15 Execution timed out 3021 ms 2424 KB Time limit exceeded
16 Execution timed out 3043 ms 2552 KB Time limit exceeded
17 Execution timed out 3054 ms 2424 KB Time limit exceeded
18 Incorrect 50 ms 2424 KB Output isn't correct
19 Execution timed out 3030 ms 2552 KB Time limit exceeded
20 Execution timed out 3051 ms 2552 KB Time limit exceeded