Submission #1012074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012074		DeadlyCritic	Sailing Race (CEOI12_race)	C++17	0 / 100	279 ms	63952 KiB

race

#include <bits/stdc++.h>

#define cif(i, n) for(int i = 0; i < n; i++)
#define pif(i, n) for(int i = n-1; i >= 0; i--)
#define scan(a, __n) for(int __ = 0; __ < __n; __++)cin >> a[__];
// #define print(a, __n) for(int ___ = 0; ___ < __n; ___++)cout << a[___] << ' '; cout << '\n';
//  #define int ll

#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);

// #define fr first
// #define sc second
 
#define all(v) v.begin(), v.end()
 
#define c0 (v<<1)
#define c1 (c0|1)
#define md ((l+r)/2)
 
typedef long long ll;
typedef double ld;


using namespace std;

const int mod = 1e9+7;
const int maxN = 1e6+7;
const string fileName = "";

// const int maxFac = 1e6+7; 
// ll fac[maxFac], _fac[maxFac];

// ll po(ll b, ll p){
//     b %= mod;
//     p %= mod-1;
//     ll r = 1;
//     while(p){
//         if(p&1)r = r*b%mod;
//         p >>= 1;
//         b = b*b%mod;
//     }
//     return r;
// }

// ll choose(ll k, ll n){
//     return fac[n]*_fac[k]%mod*_fac[n-k]%mod;
// }

// ll factorial(ll n, ll k){
//     ll ret = 1;
//     for(ll i = n; i >= n-k+1; i--){
//         ret = ret*i%mod;
//     }
//     return ret;
// }

vector<int> g[maxN], rg[maxN];

int n, k;
bool is_between(int l, int r, int x){
    return (l <= r) ? (l <= x && x <= r) : (x <= r || l <= x);
}

void slv(){
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        while(true){
            int x;
            cin >> x;
            if(x == 0)break;
            x--;
            g[i].push_back(x);
            rg[x].push_back(i);
        }
    }
    int ans = 0;
    int dp[n+3][n+3][2];
    int pd[n+3][n+3][2];
    vector<int> nx[n+3][n+3][2];
    memset(dp, 0, sizeof dp);
    memset(pd, 0, sizeof pd);
    int ind = 0;
    for(int l = 0; l < n; l++){
        for(int i = 0; i < n; i++){
            int j = (i+l)%n;
            if(i == j)continue;
            for(auto u : g[i]){
                if(u == i || u == j)continue;
                if(is_between(i, j, u)){
                    dp[i][j][0] = max(dp[i][j][0], 1 + max(dp[u][i][1], dp[u][j][0]));
                }
            }
            pd[i][j][0] = dp[i][j][0];
            int inc[n];
            memset(inc, 0, sizeof inc);
            for(auto u : g[i]){
                if(u == i || u == j)continue;
                if(is_between(i, j, u)){
                    if(pd[i][j][0] < 1 + pd[u][j][0]){
                        for(auto u : nx[u][j][0])inc[u] = 1;
                    }
                }
            }
            if(dp[i][j][0] == 0){
                for(auto u : rg[i])inc[u] = 1;
            }
            inc[i] = inc[j] = 0;
            for(int q = 0; q < n; q++){
                if(inc[i]){
                    nx[i][j][0].push_back(q);
                }
            }
            if(nx[i][j][0].size()){
                pd[i][j][0]++;
            }
            int aa = ans;
            ans = max(ans, 1 + dp[i][j][0]);
            if(k)ans = max(ans, 1 + pd[i][j][0]);
            if(aa != ans){
                if(nx[i][j][0].size()){
                    ind = nx[i][j][0][0];
                }
                else ind = i;
            }
        }
        for(int i = 0; i < n; i++){
            int j = (i-l+n)%n;
            if(i == j)continue;
            for(auto u : g[i]){
                if(u == i || u == j)continue;
                if(!is_between(i, j, u)){
                    dp[i][j][1] = max(dp[i][j][1], 1 + max(dp[u][i][0], dp[u][j][1]));
                }
            }
            pd[i][j][1] = dp[i][j][1];
            int inc[n];
            memset(inc, 0, sizeof inc);
            for(auto u : g[i]){
                if(u == i || u == j)continue;
                if(!is_between(i, j, u)){
                    if(pd[i][j][1] < 1 + pd[u][j][1]){
                        for(auto u : nx[u][j][1])inc[u] = 1;
                    }
                }
            }
            if(dp[i][j][1] == 0){
                for(auto u : g[i])inc[u] = 1;
            }
            inc[i] = inc[j] = 0;
            for(int q = 0; q < n; q++){
                if(inc[i]){
                    nx[i][j][1].push_back(q);
                }
            }
            if(nx[i][j][1].size()){
                pd[i][j][1]++;
            }
            int aa = ans;
            ans = max(ans, 1 + dp[i][j][1]);
            if(k)ans = max(ans, 1 + pd[i][j][1]);
            if(aa != ans){
                if(nx[i][j][1].size()){
                    ind = nx[i][j][1][0];
                }
                else ind = i;
            }
        }
    }

    cout << ans << '\n';
    cout << ind+1 << '\n';
}

/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0
*/

signed main(){
    if(fileName.size() > 0){
        freopen("team.in", "r", stdin);
        freopen("team.out", "w", stdout);
    }

    fastIO;
    // cout << fixed << setprecision (15);


    // fac[0] = 1;
    // for(int i = 1; i < maxFac; i++)fac[i] = fac[i-1]*i%mod;
    // _fac[maxFac-1] = po(fac[maxFac-1], mod-2);
    // for(int i = maxFac-2; i >= 0; i--)_fac[i] = _fac[i+1]*(i+1)%mod;

    // w[0] = 1;
    // for(int i = 1; i < maxN; i++)w[i] = w[i-1]*p%mod;
    // _w[maxN-1] = po(w[maxN-1], mod-2);
    // for(int i = maxN-2; i >= 0; i--)_w[i] = _w[i+1]*p%mod;
    
    
    int t = 1;
    // cin >> t;
    while(t--){
        // cout << slv() << '\n';
        slv();
        // string s;
        // cin >> s;
        // bool x = slv();
        // cout << (x?"YES":"NO") << '\n';
    }
}       
/*

*/

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |         freopen("team.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
race.cpp:188:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |         freopen("team.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100