oj.uz

Submission #89466

# Submission time Handle Problem Language Result Execution time Memory
89466 2018-12-15T02:32:38 Z updown1 Sailing Race (CEOI12_race) C++17
40 / 100
 297 ms 5072 KB 
/*
dp[node 1][node 2][0/1] = max edges in the range starting at node 1/2 (based on the third dimension)
big[node 1][node 2] = max edges if any range from node 1 to node 2
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, N)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define int ll
const int MAXN=500, INF=1000000000000000000;
///500,000,000
int N, K, dp[MAXN][MAXN][2], out, loc;
vector<int> adj[MAXN];

bool in (int x, int y, int z) {
    if (y < z) return y < x && x < z;
    return x > y || x < z;
}
int solve(int n1, int n2, int at) {
    if (dp[n1][n2][at] != -1) return dp[n1][n2][at];
    dp[n1][n2][at] = 0;
    //w<< n1 s n2 s at<<e;
    /// range is n1+1 to n2-1  (n1+1)%N to (n2-1+N)%N
    if ((n1+1)%N == n2) {dp[n1][n2][at] = 0; return dp[n1][n2][at];}
    if (at == 0) {
        /// at n1
        for (int i: adj[n1]) if (in(i, n1, n2)) {
            dp[n1][n2][0] = max(dp[n1][n2][0], max(solve(n1, i, 1), solve(i, n2, 0))+1);
        }
        return dp[n1][n2][0];
    }
    /// at n2
    for (int i: adj[n2]) if (in(i, n1, n2)) {
        dp[n1][n2][1] = max(dp[n1][n2][1], max(solve(i, n2, 0), solve(n1, i, 1))+1);
    }
    return dp[n1][n2][1];
}


main() {
    //ifstream cin("test.in");
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> K;
	ffi {int a; cin >> a; while (a != 0) {adj[i].pb(a-1); cin >> a;}}
	ffa dp[i][j][0] = dp[i][j][1] = -1;
	ffa {solve(i, j, 0); solve(i, j, 1);}
	if (/*K == 0*/true) ffi{
        if (dp[i][i][0] > out) {out = dp[i][i][0]; loc = i+1;}
	}
	else {
        ffi for (int j: adj[i]) {
            if (1+dp[j][j][0] > out) {out = dp[j][j][0]+1; loc = i+1;}
        }
	}
	//ffa w<< i+1 s j+1 c solve(i, j, 0) s solve(i, j, 1)<<e;
	w<< out <<e<< loc<<e;
}

Compilation message

race.cpp:51:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 500 KB Output isn't correct
3 Incorrect 2 ms 656 KB Output isn't correct
4 Incorrect 3 ms 656 KB Output isn't correct
5 Correct 3 ms 744 KB Output is correct
6 Incorrect 3 ms 744 KB Output isn't correct
7 Correct 5 ms 868 KB Output is correct
8 Incorrect 4 ms 868 KB Output isn't correct
9 Correct 6 ms 996 KB Output is correct
10 Correct 13 ms 1124 KB Output is correct
11 Correct 9 ms 1208 KB Output is correct
12 Incorrect 22 ms 2064 KB Output isn't correct
13 Incorrect 45 ms 2964 KB Output isn't correct
14 Correct 71 ms 3788 KB Output is correct
15 Incorrect 206 ms 4876 KB Output isn't correct
16 Incorrect 263 ms 4880 KB Output isn't correct
17 Incorrect 196 ms 4880 KB Output isn't correct
18 Correct 111 ms 4880 KB Output is correct
19 Incorrect 297 ms 5072 KB Output isn't correct
20 Incorrect 286 ms 5072 KB Output isn't correct