oj.uz

답안 #143361

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143361 2019-08-13T19:33:51 Z popovicirobert Sailing Race (CEOI12_race) C++14
40 / 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;

bool edge[MAXN][MAXN];

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--;
            edge[i][x] = 1;
            g[i].push_back(x);
            cin >> x;
        }
    }

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

    for(int len = 2; len < n; len++) {
        for(i = 0; i < n; i++) {
            j = get(i + len);
            for(int k = nxt(i); k != j; k = nxt(k)) {
                int cur = 1 + max(dp[i][k][1], dp[k][j][0]);
                if(edge[i][k]) dp[i][j][0] = max(dp[i][j][0], cur);
                if(edge[j][k]) dp[i][j][1] = max(dp[i][j][1], cur);
            }
        }
    }

    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++) {
            if(edge[i][j]) {
                combine(ans, {max(dp[j][i][0], dp[i][j][1]) + 1, i});
            }
        }
    }
    if(k == 0) {
        cout << ans.first << "\n" << ans.second + 1;
        return 0;
    }

    for(int len = 1; len < n - 1; len++) {
        for(i = 0; i < n; i++) {
            j = get(i + len);
            dp[i][nxt(j)][0] = max(dp[i][nxt(j)][0], dp[i][j][0]);
            dp[prv(i)][j][1] = max(dp[prv(i)][j][1], dp[i][j][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
40.0 / 100.0

# 결과 실행 시간 메모리 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 504 KB Output isn't correct
4 Incorrect 3 ms 504 KB Output isn't correct
5 Correct 3 ms 508 KB Output is correct
6 Incorrect 9 ms 632 KB Output isn't correct
7 Correct 4 ms 632 KB Output is correct
8 Incorrect 11 ms 760 KB Output isn't correct
9 Correct 7 ms 760 KB Output is correct
10 Correct 6 ms 888 KB Output is correct
11 Correct 9 ms 860 KB Output is correct
12 Incorrect 299 ms 1272 KB Output isn't correct
13 Incorrect 478 ms 1912 KB Output isn't correct
14 Correct 286 ms 2168 KB Output is correct
15 Execution timed out 3035 ms 2680 KB Time limit exceeded
16 Execution timed out 3028 ms 2808 KB Time limit exceeded
17 Execution timed out 3052 ms 2680 KB Time limit exceeded
18 Correct 280 ms 2680 KB Output is correct
19 Execution timed out 3042 ms 2808 KB Time limit exceeded
20 Execution timed out 3044 ms 2808 KB Time limit exceeded