Submission #1106789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106789		Icelast	Sailing Race (CEOI12_race)	C++17	40 / 100	705 ms	5124 KiB

race

#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 / 100