oj.uz

Submission #832758

# Submission time Handle Problem Language Result Execution time Memory
832758 2023-08-21T14:32:04 Z TS_2392 Sailing Race (CEOI12_race) C++14
40 / 100
 445 ms 3456 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], dp2[N][N][2];
int main(){
   	SPEED;
    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;
        }
    }
    cout << res << '\n' << res_vtx;
    return 0;
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Incorrect 1 ms 460 KB Output isn't correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 2 ms 596 KB Output isn't correct
7 Correct 2 ms 724 KB Output is correct
8 Incorrect 2 ms 724 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 6 ms 948 KB Output is correct
12 Incorrect 28 ms 1532 KB Output isn't correct
13 Incorrect 79 ms 2132 KB Output isn't correct
14 Correct 166 ms 2728 KB Output is correct
15 Incorrect 384 ms 3388 KB Output isn't correct
16 Incorrect 412 ms 3444 KB Output isn't correct
17 Incorrect 382 ms 3408 KB Output isn't correct
18 Correct 301 ms 3320 KB Output is correct
19 Incorrect 439 ms 3452 KB Output isn't correct
20 Incorrect 445 ms 3456 KB Output isn't correct