답안 #687824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
687824	2023-01-27T02:04:54 Z	2vas	Sailing Race (CEOI12_race)	C++17	0 / 100	387 ms	8528 KB

race

#include <bits/stdc++.h>
using namespace std;

void solve();

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t=1; // cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

int n;
bool inOrder(int a, int b, int c) {
    int d1 = b - a;
    if (d1 < 0) d1 += n;
    int d2 = c - a;
    if (d2 < 0) d2 += n;
    return d2 > d1;
}

void solve() {    
    int k; cin >> n >> k;

    set<int> edges[n];
    set<int> reversed_edges[n];
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        while (x != 0) {
            x--;
            edges[i].insert(x);
            reversed_edges[x].insert(i);
            // cout << i << ' ' << x << endl;
            cin >> x;
        }
    }

    // dp[prev][cur][1 if prev->cur, 0 if cur->prev]
    // is the length of longest not including prev -> cur
    int dp[n][n][2];
    memset(dp, 0, sizeof(dp));

    pair<int, int> best = make_pair(0,0);
    int bestBit = 0;
    for (int j = 1; j < n; j++) {
        // j is the distance between the two relavent nodes
        for (int i = 0; i < n; i++) {
            // compute dp[i][i+j][1] and dp[i+j][i][0]
            int k = i + j;
            if (k >= n) { k -= n; }
            
            // dp[i][k][1]
            for (int v : edges[k]) {
                if (!inOrder(i, v, k)) continue;

                dp[i][k][1] = max(dp[i][k][1], 1 + dp[k][v][0] );
                dp[i][k][1] = max(dp[i][k][1], 1 + dp[i][v][1] );
            }

            if (dp[best.first][best.second][bestBit] < dp[i][k][1] && edges[i].find(k) != edges[i].end()) {
                best = make_pair(i, k);
                bestBit = 1;
            }
            
            // dp[k][i][0]
            for (int v : edges[i]) {
                if (!inOrder(i, v, k)) continue;
                
                dp[k][i][0] = max(dp[k][i][0], 1 + dp[k][v][0]);
                dp[k][i][0] = max(dp[k][i][0], 1 + dp[i][v][1]);
            }
            

            if (dp[best.first][best.second][bestBit] < dp[k][i][0] && edges[k].find(i) != edges[k].end()) {
                best = make_pair(k, i);
                bestBit = 0;
            }
            
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << dp[i][j][1] << ' ';
        }
        cout << endl;
    }
    cout << endl;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << dp[i][j][0] << ' ';
        }
        cout << endl;
    }
    cout << endl;

    cout << dp[best.first][best.second][bestBit] + 1 << endl;
    cout << best.first + 1 << endl;



}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Incorrect	1 ms	212 KB	Output isn't correct
3	Incorrect	1 ms	212 KB	Output isn't correct
4	Incorrect	1 ms	340 KB	Output isn't correct
5	Incorrect	1 ms	340 KB	Output isn't correct
6	Incorrect	2 ms	448 KB	Output isn't correct
7	Incorrect	4 ms	596 KB	Output isn't correct
8	Incorrect	3 ms	468 KB	Output isn't correct
9	Incorrect	6 ms	724 KB	Output isn't correct
10	Incorrect	16 ms	1364 KB	Output isn't correct
11	Incorrect	9 ms	852 KB	Output isn't correct
12	Incorrect	24 ms	1388 KB	Output isn't correct
13	Incorrect	46 ms	2168 KB	Output isn't correct
14	Incorrect	77 ms	3440 KB	Output isn't correct
15	Incorrect	259 ms	6720 KB	Output isn't correct
16	Incorrect	291 ms	7568 KB	Output isn't correct
17	Incorrect	235 ms	6716 KB	Output isn't correct
18	Incorrect	106 ms	4680 KB	Output isn't correct
19	Incorrect	372 ms	8528 KB	Output isn't correct
20	Incorrect	387 ms	8388 KB	Output isn't correct