Submission #89463

# Submission time Handle Problem Language Result Execution time Memory
89463 2018-12-15T01:53:48 Z updown1 Sailing Race (CEOI12_race) C++17
40 / 100
84 ms 6272 KB
/*
dp[node 1][node 2][0/1] = max edges in the range starting at node 1/2 (based on the third dimension)
*/
#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;
	if (K == 0) ffi{
        solve(i, i, 0);
        if (dp[i][i][0] > out) {out = dp[i][i][0]; loc = i+1;}
        //w<< i+1 s dp[i][i][0]<<e;
	}
	//ffa w<< i+1 s j+1 c solve(i, j, 0) s solve(i, j, 1)<<e;
	w<< out s loc<<e;
}

Compilation message

race.cpp:50:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 720 KB Output isn't correct
3 Incorrect 3 ms 720 KB Output isn't correct
4 Incorrect 2 ms 832 KB Output isn't correct
5 Correct 3 ms 1028 KB Output is correct
6 Incorrect 2 ms 1028 KB Output isn't correct
7 Correct 5 ms 1100 KB Output is correct
8 Incorrect 2 ms 1112 KB Output isn't correct
9 Correct 5 ms 1244 KB Output is correct
10 Correct 13 ms 1528 KB Output is correct
11 Correct 8 ms 1528 KB Output is correct
12 Incorrect 4 ms 2448 KB Output isn't correct
13 Incorrect 5 ms 3404 KB Output isn't correct
14 Correct 63 ms 4200 KB Output is correct
15 Incorrect 8 ms 5392 KB Output isn't correct
16 Incorrect 10 ms 5628 KB Output isn't correct
17 Incorrect 8 ms 5692 KB Output isn't correct
18 Correct 84 ms 5692 KB Output is correct
19 Incorrect 10 ms 6100 KB Output isn't correct
20 Incorrect 10 ms 6272 KB Output isn't correct