Submission #1012092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012092		DeadlyCritic	Sailing Race (CEOI12_race)	C++17	20 / 100	336 ms	19288 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 = 500+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;
// }


int dp[maxN][maxN][2];
int pd[maxN][maxN][2];
int fdp[maxN][maxN][2];
vector<int> nx[maxN][maxN][2];

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

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

int ans, ind;

void cal(int i, int j, int dir){
    fdp[i][j][dir] = i;
    for(auto u : rg[i]){
        if(u == i || u == j)continue;
        if(is_between(i, j, u, dir)){
            dp[i][j][dir] = max(dp[i][j][dir], 1 + max(dp[u][i][1-dir], dp[u][j][dir]));
            if(1+dp[u][i][1-dir] == dp[i][j][dir]){
                fdp[i][j][dir] = fdp[u][i][1-dir];
            }
            if(1+dp[u][j][dir] == dp[i][j][dir]){
                fdp[i][j][dir] = fdp[u][j][dir];
            }
        }
    }
    pd[i][j][dir] = dp[i][j][dir];
    int inc[n];
    memset(inc, 0, sizeof inc);
    for(auto u : rg[i]){
        if(u == i || u == j)continue;
        if(is_between(i, j, u, dir)){
            if(pd[i][j][dir] < 1 + pd[u][j][dir]){
                for(auto v : nx[u][j][dir]){
                    if(is_between(i, j, v, 1-dir)){
                        inc[v] = 1;
                    }
                }
            }
        }
    }
    if(dp[i][j][dir] == 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][dir].push_back(q);
        }
    }
    if(nx[i][j][dir].size()){
        pd[i][j][dir]++;
    }
    int aa = ans;
    ans = max(ans, 1 + dp[i][j][dir]);
    if(k)ans = max(ans, 1 + pd[i][j][dir]);
    if(aa != ans){
        if(nx[i][j][dir].size()){
            ind = nx[i][j][dir][0];
        }
        else ind = fdp[i][j][dir];
    }
}

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);
        }
    }
    for(int l = 0; l < n; l++){
        for(int i = 0, j; i < n; i++){
            j = (i+l)%n;
            cal(i, j, 0);
            j = (i-l+n)%n;
            cal(i, j, 1);
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            // cout << i << ' ' << j << " : ";
            // cout << dp[i][j][0] << ' ' << pd[i][j][0] << ' ' << fdp[i][j][0] << " | " << dp[i][j][1] << ' ' << pd[i][j][1] << ' ' << fdp[i][j][1] << '\n';
        }
    }

    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:169:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         freopen("team.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
race.cpp:170:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         freopen("team.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 100