oj.uz

답안 #143317

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143317 2019-08-13T15:52:05 Z popovicirobert Sailing Race (CEOI12_race) C++14
0 / 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(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;
        while(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
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3043 ms 376 KB Time limit exceeded
2 Incorrect 2 ms 376 KB Output isn't correct
3 Incorrect 2 ms 504 KB Output isn't correct
4 Incorrect 4 ms 504 KB Output isn't correct
5 Execution timed out 3032 ms 504 KB Time limit exceeded
6 Incorrect 9 ms 504 KB Output isn't correct
7 Execution timed out 3073 ms 636 KB Time limit exceeded
8 Incorrect 10 ms 632 KB Output isn't correct
9 Execution timed out 3014 ms 760 KB Time limit exceeded
10 Execution timed out 3041 ms 760 KB Time limit exceeded
11 Execution timed out 3007 ms 764 KB Time limit exceeded
12 Incorrect 273 ms 1272 KB Output isn't correct
13 Incorrect 410 ms 1528 KB Output isn't correct
14 Execution timed out 3027 ms 2040 KB Time limit exceeded
15 Execution timed out 3054 ms 2424 KB Time limit exceeded
16 Execution timed out 3036 ms 2552 KB Time limit exceeded
17 Execution timed out 3070 ms 2424 KB Time limit exceeded
18 Execution timed out 3037 ms 2424 KB Time limit exceeded
19 Execution timed out 3053 ms 2552 KB Time limit exceeded
20 Execution timed out 3060 ms 2552 KB Time limit exceeded