oj.uz

답안 #1106789

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1106789 2024-10-31T04:34:17 Z Icelast Sailing Race (CEOI12_race) C++17
40 / 100
 705 ms 5124 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 1e9+9;
void solve(){
    int n, k;
    cin >> n >> k;
    vector<vector<int>> adj(n+1), adj_rev(n+1);
    vector<vector<bool>> mat(n+1, vector<bool>(n+1, false));
    for(int i = 1; i <= n; i++){
        while(true){
            int x;
            cin >> x;
            if(x == 0) break;
            adj[i].push_back(x);
            adj_rev[x].push_back(i);
            mat[i][x] = true;
        }
    }
    vector<int> prv(n+1), nxt(n+1);
    for(int i = 1; i <= n; i++){
        prv[i] = i-1;
        if(prv[i] == 0) prv[i] = n;
        nxt[i] = i+1;
        if(nxt[i] == n+1) nxt[i] = 1;
    }
    vector<vector<int>> f(n+1, vector<int>(n+1, 0)), g(n+1, vector<int>(n+1, 0)), mf(n+1, vector<int>(n+1, -INF)), mg(n+1, vector<int>(n+1, -INF));
    //f is counter clockwise, g is clockwise such that path in region [i, j] start point is i, end point arbitrary
    //mf is counter clockwise, mg is clockwise such that path in region [i, j], start point is i, end point is j
    for(int i = 1; i <= n; i++){
        for(int j : adj[i]){
            f[i][j] = 1;
            g[i][j] = 1;
            mf[i][j] = 1;
            mg[i][j] = 1;
        }
    }
    auto chmax = [&](int &a, int b) -> void{
        a = max(a, b);
    };
    for(int len = 2; len < n; len++){
        for(int i = 1; i <= n; i++){
            int j = i+len;
            if(j > n) j-=n;
            int k;
            int nxt_i = i+1, prv_i = i-1;
            if(nxt_i > n) nxt_i-=n;
            if(prv_i == 0) prv_i+=n;
            for(k = i; ; k++){
                if(k == n+1){
                    k = 1;
                }else if(k == 0){
                    k = n;
                }

                if(mat[i][k] == 1) chmax(f[i][j], mat[i][k]+max(f[k][j], g[k][nxt_i]));
                chmax(mf[i][j], mf[i][k] + mf[k][j]);
                if(k == j) break;
            }
            j = i-len;
            if(j < 1) j+=n;
            for(k = i; ; k--){
                if(k == n+1){
                    k = 1;
                }else if(k == 0){
                    k = n;
                }
                if(mat[i][k] == 1) chmax(g[i][j], mat[i][k]+max(g[k][j], f[k][prv_i]));
                chmax(mg[i][j], mg[i][k] + mg[k][j]);
                if(k == j) break;
            }
        }
    }
    if(k == 0){
        int ans = -1, ansi = -1;
        for(int i = 1; i <= n; i++){
            int j = i-1;
            if(j == 0) j+=n;
            if(ans < f[i][j]){
                ans = f[i][j];
                ansi = i;
            }
            j = i+1;
            if(j == n+1) j-=n;
            if(ans < g[i][j]){
                ans = g[i][j];
                ansi = i;
            }
        }
        cout << ans << "\n" << ansi;
        return;
    }
    auto dist = [&](int i, int j) -> int{
        if(j < i) j+=n;
        return j-i;
    };
    auto distc = [&](int i, int j) -> int{
        if(i < j) i+=n;
        return i-j;
    };
    int ans = -1, ansi = -1;
    for(int B = 1; B <= n; B++){
        for(int C = 1; C <= n; C++){
            if(B == C) continue;
            int A = -1, mn = 1e9;
            for(int it : adj_rev[B]){
                if(dist(C, it) < mn){
                    mn = dist(C, it);
                    A = it;
                }
            }
            if(A == -1 || dist(B, A)+dist(A,C) == dist(B, C)) continue;
            for(int D : adj[C]){
                if(dist(A, D)+dist(D, B) != dist(A, B)) continue;
                int cost = 1 + mf[B][C] + 1 + max(g[D][nxt[A]], f[D][prv[B]]);
                if(ans < cost){
                    ans = cost;
                    ansi = A;
                }
            }
        }
    }
    for(int B = 1; B <= n; B++){
        for(int C = 1; C <= n; C++){
            if(B == C) continue;
            int A = -1, mn = 1e9;
            for(int it : adj_rev[B]){
                if(distc(C, it) < mn){
                    mn = distc(C, it);
                    A = it;
                }
            }
            if(A == -1 || distc(B, A)+distc(A, C) == distc(B, C)) continue;
            for(int D : adj[C]){
                if(distc(A, D)+distc(D, B) != distc(A, B)) continue;
                int cost = 1 + mg[B][C] + 1 + max(f[D][prv[A]], g[D][nxt[B]]);
                if(ans < cost){
                    ans = cost;
                    ansi = A;
                }
            }
        }
    }
    cout << ans << "\n" << ansi;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("main.inp", "r", stdin);
    //freopen("main.out", "w", stdout);
    solve();
}

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 504 KB Output isn't correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Incorrect 1 ms 336 KB Output isn't correct
5 Correct 1 ms 504 KB Output is correct
6 Incorrect 3 ms 336 KB Output isn't correct
7 Correct 3 ms 592 KB Output is correct
8 Incorrect 3 ms 592 KB Output isn't correct
9 Correct 5 ms 592 KB Output is correct
10 Correct 5 ms 592 KB Output is correct
11 Correct 6 ms 592 KB Output is correct
12 Incorrect 39 ms 1208 KB Output isn't correct
13 Incorrect 111 ms 1872 KB Output isn't correct
14 Correct 218 ms 3152 KB Output is correct
15 Incorrect 551 ms 4936 KB Output isn't correct
16 Incorrect 630 ms 5088 KB Output isn't correct
17 Incorrect 562 ms 4688 KB Output isn't correct
18 Correct 396 ms 4700 KB Output is correct
19 Incorrect 705 ms 5124 KB Output isn't correct
20 Incorrect 667 ms 4944 KB Output isn't correct