oj.uz

답안 #143353

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143353 2019-08-13T18:18:38 Z popovicirobert Sailing Race (CEOI12_race) C++14
5 / 100
 3000 ms 2556 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]));
                }
                if(k < i || k > j) {
                    dp[j][i][0] = max(dp[j][i][0], 1 + max(dp[j][k][1], dp[k][i][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]));
                }
                if(k < i || k > j) {
                    dp[j][i][1] = max(dp[j][i][1], 1 + max(dp[j][k][1], dp[k][i][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 = 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});
                }
                if(k == i) {
                    break;
                }
            }

            fill(best, best + n, -INF);
            best[j] = 0;
            for(int k = j; ; 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});
                }
                if(k == i) {
                    break;
                }
            }
        }
    }
    cout << ans.first << "\n" << ans.second + 1;


    return 0;
}

Subtask #1
5.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't 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 2 ms 504 KB Output isn't correct
6 Incorrect 9 ms 508 KB Output isn't correct
7 Incorrect 4 ms 632 KB Output isn't correct
8 Incorrect 10 ms 604 KB Output isn't correct
9 Incorrect 4 ms 760 KB Output isn't correct
10 Correct 7 ms 760 KB Output is correct
11 Incorrect 5 ms 760 KB Output isn't correct
12 Incorrect 283 ms 1244 KB Output isn't correct
13 Incorrect 428 ms 1528 KB Output isn't correct
14 Incorrect 29 ms 2040 KB Output isn't correct
15 Execution timed out 3044 ms 2424 KB Time limit exceeded
16 Execution timed out 3038 ms 2552 KB Time limit exceeded
17 Execution timed out 3039 ms 2424 KB Time limit exceeded
18 Incorrect 38 ms 2296 KB Output isn't correct
19 Execution timed out 3054 ms 2552 KB Time limit exceeded
20 Execution timed out 3038 ms 2556 KB Time limit exceeded