oj.uz

Submission #143318

# Submission time Handle Problem Language Result Execution time Memory
143318 2019-08-13T15:57:38 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][0], 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 3 ms 504 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 632 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 764 KB Output isn't correct
10 Correct 8 ms 764 KB Output is correct
11 Incorrect 5 ms 760 KB Output isn't correct
12 Incorrect 265 ms 1144 KB Output isn't correct
13 Incorrect 406 ms 1628 KB Output isn't correct
14 Incorrect 36 ms 2168 KB Output isn't correct
15 Execution timed out 3052 ms 2424 KB Time limit exceeded
16 Execution timed out 3044 ms 2552 KB Time limit exceeded
17 Execution timed out 3039 ms 2424 KB Time limit exceeded
18 Incorrect 47 ms 2296 KB Output isn't correct
19 Execution timed out 3054 ms 2552 KB Time limit exceeded
20 Execution timed out 3042 ms 2552 KB Time limit exceeded