Submission #832320

#	Time	Username	Problem	Language	Result	Execution time	Memory
832320		TS_2392	Sailing Race (CEOI12_race)	C++14	20 / 100	1083 ms	5312 KiB

race

#include <bits/stdc++.h>
using namespace std;

#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED {ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);}
template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}

const int N = 505   ;
int n, type, res, res_vtx, nxt[N], prv[N];
int adj[N][N], dp1[N][N][2], dp2[N][N][2];
int main(){
    fileIO("text");
    cin >> n >> type;
    for(int u = 1, v; u <= n; ++u){
        cin >> v;
		while(v){
			adj[u][v] = 1;
			cin >> v;
		}
        nxt[u] = u + 1; prv[u] = u - 1;
    }
    nxt[n] = 1; prv[1] = n;
    for(int len = 2; len < n; ++len){
        for(int i = 1; i <= n; ++i){
            int j = i + len - 1;
            if(j > n) j -= n;

            if(adj[i][j]) dp1[i][j][0] = 1;
            for(int k = nxt[i]; k != j; k = nxt[k]) if(adj[k][j] && dp1[i][k][0]){
                maximize(dp1[i][j][0], dp1[i][k][0] + 1);
            }

            if(adj[j][i]) dp1[i][j][1] = 1;
            for(int k = prv[j]; k != i; k = prv[k]) if(adj[k][i] && dp1[k][j][1]){
                maximize(dp1[i][j][1], dp1[k][j][1] + 1);
            }

        }
    }
    for(int len = 2; len < n; ++len){
        for(int i = 1; i <= n; ++i){
            int j = i + len - 1;
            if(j > n) j -= n;

            dp2[i][j][0] = dp2[i][prv[j]][0];
            if(adj[i][j]) maximize(dp2[i][j][0], dp2[nxt[i]][j][1] + 1);
            for(int k = nxt[i]; k != j; k = nxt[k]) if(adj[k][j] && dp1[i][k][0]){
                maximize(dp2[i][j][0], dp1[i][k][0] + dp2[k][j][0]);
            }

            dp2[i][j][1] = dp2[nxt[i]][j][1];
            if(adj[j][i]) maximize(dp2[i][j][1], dp2[i][prv[j]][0] + 1);
            for(int k = prv[j]; k != i; k = prv[k]) if(adj[k][i] && dp1[k][j][1]){
                maximize(dp2[i][j][1], dp1[k][j][1] + dp2[i][k][1]);
            }

            if(maximize(res, dp2[i][j][0])) res_vtx = i;
            if(maximize(res, dp2[i][j][1])) res_vtx = j;
        }
    }
    cout << res << '\n' << res_vtx;
    return 0;
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:4:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:13:5: note: in expansion of macro 'fileIO'
   13 |     fileIO("text");
      |     ^~~~~~
race.cpp:4:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:13:5: note: in expansion of macro 'fileIO'
   13 |     fileIO("text");
      |     ^~~~~~

• Subtask 1: 20 / 100