oj.uz

Submission #835088

# Submission time Handle Problem Language Result Execution time Memory
835088 2023-08-23T07:59:23 Z TS_2392 Sailing Race (CEOI12_race) C++14
65 / 100
 1621 ms 5508 KB 
#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], dp[N][N][2], f[N][N][2];
int main(){
   	SPEED; 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;
            //compute dp[i][j][0]
            if(adj[i][j]) dp[i][j][0] = 1 + dp[j][nxt[i]][1];
            for(int k = i; k != j; k = nxt[k]) if(adj[i][k]){
                maximize(dp[i][j][0], max(dp[k][j][0], dp[k][nxt[i]][1]) + 1);
            }
            //compute dp[j][i][1]
            if(adj[j][i]) dp[j][i][1] = 1 + dp[i][prv[j]][0];
            for(int k = j; k != i; k = prv[k]) if(adj[j][k]){
                maximize(dp[j][i][1], max(dp[k][prv[j]][0], dp[k][i][1]) + 1);
            }

            if(maximize(res, dp[i][j][0])) res_vtx = i;
            if(maximize(res, dp[j][i][1])) res_vtx = j;
        }
    }
    if(type){
        for(int len = 2; len <= n; ++len){
            for(int i = 1; i <= n; ++i){
                int j = i + len - 1;
                if(j > n) j -= n;
                //compute f[i][j][0];
                if(adj[i][j]) f[i][j][0] = 1;
                for(int k = i; k != j; k = nxt[k]) if(adj[i][k] && f[k][j][0]){
                    maximize(f[i][j][0], f[k][j][0] + 1);
                }
                //compute f[j][i][1]
                if(adj[j][i]) f[j][i][1] = 1;
                for(int k = j; k != i; k = prv[k]) if(adj[j][k] && f[k][i][1]){
                    maximize(f[j][i][1], f[k][i][1] + 1);
                }
            }
        }
        for(int a = 1; a <= n; ++a){
            for(int b = nxt[a]; b != a; b = nxt[b]){
                for(int c = nxt[a], ma = -1; c != b; c = nxt[c]){
                    if(adj[a][c] && ma >= 0 && f[c][b][0]){
                        if(maximize(res, f[c][b][0] + 2 + ma)) res_vtx = a;
                    }
                    if(adj[b][c]) maximize(ma, dp[c][nxt[a]][1]);
                }
                for(int c = prv[a], ma = -1; c != b; c = prv[c]){
                    if(adj[a][c] && ma >= 0 && f[c][b][1]){
                        if(maximize(res, f[c][b][1] + 2 + ma)) res_vtx = a;
                    }
                    if(adj[b][c]) maximize(ma, dp[c][prv[a]][0]);
                }
            }
        }
    }
    cout << res << '\n' << res_vtx;
    return 0;
}

Compilation message

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:12: note: in expansion of macro 'fileIO'
   13 |     SPEED; 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:12: note: in expansion of macro 'fileIO'
   13 |     SPEED; fileIO("text");
      |            ^~~~~~

Subtask #1
65.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 1 ms 596 KB Output isn't correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 4 ms 852 KB Output isn't correct
7 Correct 2 ms 724 KB Output is correct
8 Incorrect 7 ms 1108 KB Output isn't correct
9 Correct 5 ms 852 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 8 ms 1024 KB Output is correct
12 Incorrect 97 ms 2324 KB Output isn't correct
13 Incorrect 253 ms 3316 KB Output isn't correct
14 Correct 167 ms 2764 KB Output is correct
15 Correct 1269 ms 5368 KB Output is correct
16 Correct 1444 ms 5508 KB Output is correct
17 Incorrect 1288 ms 5316 KB Output isn't correct
18 Correct 293 ms 3328 KB Output is correct
19 Incorrect 1621 ms 5428 KB Output isn't correct
20 Correct 1578 ms 5436 KB Output is correct