oj.uz

답안 #37293

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37293 2017-12-23T14:43:50 Z DoanPhuDuc Sailing Race (CEOI12_race) C++
80 / 100
 2206 ms 11460 KB 
#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
#define BitCount(x) __builtin_popcount(x)

using namespace std;

typedef long long LL;
typedef pair <int, int> II;

const int N = 5e2 + 10;
const int INF = 0x3f3f3f3f;

int n, request;
int CL1[N][N], CL2[N][N];
int dp[N][N][2], f[N][N][2], g[N][N][2];

bool e[N][N];
bool fre[N][N][2];

vector <int> adj[N], rev[N];

int O;

int CCW(int i, int j, int k) {
    if (i == k || j == k || i == j) return -1;
    if (i < j) {
        return (j < k && k < n) || (k < i);
    } else return (j < k && k < i);
}

bool CMP1(int x, int y) {
    return CCW(O, x, y);
}

bool CMP2(int x, int y) {
    return !CCW(O, x, y);
}

int DP(int l, int r, int k) {
    if (l == r) return dp[l][r][k] = 0;
    int &ans = dp[l][r][k];
    if (ans != -1) return ans;
    ans = 0;
    REP(i, 0, adj[l].size()) {
        int u = adj[l][i];
        if (CCW(l, u, r) == k) {
            ans = max(ans, 1 + DP(u, r, k));
            ans = max(ans, 1 + DP(u, l, k ^ 1));
        }
    }
    return ans;
}

int Compute(int l, int r, int k) {
    if (l == r) return 0;
    int &ans = f[l][r][k];
    if (ans != -1) return ans;
    ans = e[l][r] ? 1 : -INF;
    REP(i, 0, adj[l].size()) {
        int u = adj[l][i];
        if (CCW(l, r, u) == (k ^ 1)) {
            ans = max(ans, 1 + Compute(u, r, k));
        }
    }
    return ans;
}

void Init() {
    memset(CL1, -1, sizeof CL1);
    memset(CL2, -1, sizeof CL2);
    REP(i, 0, n) {
        O = i;
        sort(rev[i].begin(), rev[i].end(), CMP1);
        int p = 0;
        for (int j = (i + 1) % n; j != i; j = (j + 1) % n) {
            while (p < rev[i].size() && CCW(i, j, rev[i][p]) != 1) ++p;
            if (p < rev[i].size()) CL1[i][j] = rev[i][p];
        }
        sort(rev[i].begin(), rev[i].end(), CMP2);
            p = 0;
        for (int j = (i - 1 + n) % n; j != i; j = (j - 1 + n) % n) {
            while (p < rev[i].size() && CCW(i, j, rev[i][p]) != 0) ++p;
            if (p < rev[i].size()) CL2[i][j] = rev[i][p];
        }

    }
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d%d", &n, &request);
    REP(u, 0, n) {
        int v;
        while (scanf("%d", &v) == 1) {
            if (v == 0) break;
            assert(v - 1 != u);
            e[u][v - 1] = true;
            adj[u].push_back(v - 1);
            rev[v - 1].push_back(u);
        }
    }
    Init();
    memset(dp, -1, sizeof dp);
    int ans = 0, num = 0;
    REP(i, 0, n)
        REP(j, 0, n) {
            int can = DP(i, j, 0);
            if (can > ans) {
                ans = can;
                num = i;
            }
                can = DP(i, j, 1);
            if (can > ans) {
                ans = can;
                num = i;
            }
        }
    if (request == 0) {
        printf("%d\n%d", ans, num + 1);
        return 0;
    }
    memset(f, -1, sizeof f);
    REP(i, 0, n) {
        for (int j = (i + 1) % n; j != i; j = (j + 1) % n) {
            int x = Compute(i, j, 1); if (x == 0) continue;
            int k = CL1[i][j]; if (k == -1) continue;
            REP(p, 0, adj[j].size()) {
                int v = adj[j][p];
                if (CCW(j, k, v) == 1 && CCW(v, i, j) == 1) {
                    int can = 2 + x + max(DP(v, k, 0), DP(v, i, 1));
                    if (can > ans) {
                        ans = can;
                        num = k;
                    }
                }
            }
        }
        for (int j = (i - 1 + n) % n; j != i; j = (j - 1 + n) % n) {
            int x = Compute(i, j, 0); if (x == 0) continue;
            int k = CL2[i][j]; if (k == -1) continue;
            REP(p, 0, adj[j].size()) {
                int v = adj[j][p];
                if (CCW(j, k, v) == 0 && CCW(v, i, j) == 0) {
                    int can = 2 + x + max(DP(v, k, 1), DP(v, i, 0));
                    if (can > ans) {
                        ans = can;
                        num = k;
                    }
                }
            }
        }
    }
    printf("%d\n%d", ans, num + 1);
    return 0;
}

Compilation message

race.cpp: In function 'int DP(int, int, int)':
race.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
race.cpp:50:5: note: in expansion of macro 'REP'
     REP(i, 0, adj[l].size()) {
     ^
race.cpp: In function 'int Compute(int, int, int)':
race.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
race.cpp:65:5: note: in expansion of macro 'REP'
     REP(i, 0, adj[l].size()) {
     ^
race.cpp: In function 'void Init()':
race.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (p < rev[i].size() && CCW(i, j, rev[i][p]) != 1) ++p;
                      ^
race.cpp:83:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (p < rev[i].size()) CL1[i][j] = rev[i][p];
                   ^
race.cpp:88:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (p < rev[i].size() && CCW(i, j, rev[i][p]) != 0) ++p;
                      ^
race.cpp:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (p < rev[i].size()) CL2[i][j] = rev[i][p];
                   ^
race.cpp: In function 'int main()':
race.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
race.cpp:136:13: note: in expansion of macro 'REP'
             REP(p, 0, adj[j].size()) {
             ^
race.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
race.cpp:150:13: note: in expansion of macro 'REP'
             REP(p, 0, adj[j].size()) {
             ^
race.cpp:100:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &request);
                                ^

Subtask #1
80.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 10932 KB Output is correct
2 Correct 0 ms 10932 KB Output is correct
3 Correct 3 ms 10932 KB Output is correct
4 Correct 3 ms 10932 KB Output is correct
5 Correct 3 ms 10932 KB Output is correct
6 Correct 3 ms 10932 KB Output is correct
7 Incorrect 6 ms 11064 KB Output isn't correct
8 Correct 3 ms 10932 KB Output is correct
9 Incorrect 6 ms 11064 KB Output isn't correct
10 Incorrect 19 ms 11064 KB Output isn't correct
11 Incorrect 13 ms 11064 KB Output isn't correct
12 Correct 93 ms 11064 KB Output is correct
13 Correct 169 ms 11064 KB Output is correct
14 Correct 129 ms 11064 KB Output is correct
15 Correct 1139 ms 11328 KB Output is correct
16 Correct 1626 ms 11460 KB Output is correct
17 Correct 1173 ms 11328 KB Output is correct
18 Correct 146 ms 11064 KB Output is correct
19 Correct 1816 ms 11460 KB Output is correct
20 Correct 2206 ms 11460 KB Output is correct