oj.uz

답안 #143316

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143316 2019-08-13T15:48:13 Z popovicirobert Sailing Race (CEOI12_race) C++14
5 / 100
 3000 ms 2808 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(j = 0; j < n; j++) {
            combine(ans, {dp[i][j][0], i});
            combine(ans, {dp[i][j][1], j});
        }
    }
    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
5.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Incorrect 3 ms 504 KB Output isn't correct
4 Incorrect 4 ms 504 KB Output isn't correct
5 Incorrect 3 ms 552 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 10 ms 632 KB Output isn't correct
9 Incorrect 4 ms 760 KB Output isn't correct
10 Incorrect 8 ms 836 KB Output isn't correct
11 Incorrect 5 ms 760 KB Output isn't correct
12 Incorrect 273 ms 1144 KB Output isn't correct
13 Incorrect 416 ms 1528 KB Output isn't correct
14 Incorrect 36 ms 2040 KB Output isn't correct
15 Execution timed out 3050 ms 2552 KB Time limit exceeded
16 Execution timed out 3038 ms 2680 KB Time limit exceeded
17 Execution timed out 3044 ms 2552 KB Time limit exceeded
18 Incorrect 48 ms 2424 KB Output isn't correct
19 Execution timed out 3055 ms 2680 KB Time limit exceeded
20 Execution timed out 3037 ms 2808 KB Time limit exceeded