Submission #115110

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
115110	2019-06-05T10:14:58 Z	bazsi700	Sailing Race (CEOI12_race)	C++14	90 / 100	964 ms	3700 KB

race

#include <bits/stdc++.h>

using namespace std;

int dp[505][505][2];
bool nyugi[505][505][2];
vector<vector<int> > graph(505,vector<int>());
vector<vector<int> > graph2(505,vector<int>());
int n,typ;

bool between(int x, int y, int z) {
    if(z == x || z == y) {
        return false;
    }
    if(x < y) {
        return (x < z && z < y);
    } else {
        return (x < z || z < y);
    }
}

int solve(int x, int y, int way) {
    if(x == y) {
        return 0;
    }
    //cout << x << " " <<y << " " << way << endl;
    if(nyugi[x][y][way]) {
        return dp[x][y][way];
    }
    //cout << "b" << endl;
    nyugi[x][y][way] = true;
    if(!way) {
        for(int z : graph[x]) {
            if(between(x,y,z)) {
        if(x == 6 && y == 1) {
            //cout << "b" << z << endl;
        }
                dp[x][y][way] = max(dp[x][y][way],solve(x,z,1)+1);
                dp[x][y][way] = max(dp[x][y][way],solve(z,y,0)+1);
            }
        }
    } else {
    //cout << "c" << endl;
        for(int z : graph[y]) {
    //cout << "d" << y << " " << z << endl;
            if(between(x,y,z)) {
    //cout << "e" << endl;
                dp[x][y][way] = max(dp[x][y][way],solve(x,z,1)+1);
                dp[x][y][way] = max(dp[x][y][way],solve(z,y,0)+1);
            }
        }
    }
    return dp[x][y][way];
}

bool was[505];
int ans[505];
int with[505];

int check(int i, int v) {
    if(was[v]) {
        return ans[v];
    }
    was[v] = true;
    int a = -1;
    for(int j : graph2[i]) {
        if(between(v,i,j)) {
            if(a == -1 || between(v,a,j)) {
                a = j;
            }
        }
    }
    for(int u : graph[v]) {
        if(!between(i,v,u)) {
            if(ans[v] < check(i,u)+1) {
                ans[v] = check(i,u)+1;
                with[v] = with[u];
            }
            if(a != -1 && between(v,u,a)) {
                if(ans[v] < solve(u,i,0)) {
                    ans[v] = solve(u,i,0);
                    with[v] = a;
                }
                if(ans[v] < solve(a,u,1)) {
                    ans[v] = solve(a,u,1);
                    with[v] = a;
                }
            }
        }
    }
    return ans[v];
}

int check2(int i, int v) {
    if(was[v]) {
        return ans[v];
    }
    was[v] = true;
    int a = -1;
    for(int j : graph2[i]) {
        if(between(i,v,j)) {
            if(a == -1 || between(a,v,j)) {
                a = j;
            }
        }
    }
    for(int u : graph[v]) {
        if(between(i,v,u)) {
            if(ans[v] < check2(i,u)+1) {
                ans[v] = check2(i,u)+1;
                with[v] = with[u];
            }
            if(a != -1 && !between(v,u,a)) {
                if(ans[v] < solve(i,u,1)) {
                    ans[v] = solve(i,u,1);
                    with[v] = a;
                }
                if(ans[v] < solve(u,a,0)) {
                    ans[v] = solve(u,a,0);
                    with[v] = a;
                }
            }
        }
    }
    return ans[v];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> typ;
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        while(x != 0) {
            graph[i].push_back(x-1);
            graph2[x-1].push_back(i);
            cin >> x;
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
           // cout << i+1 << " " << j+1 << ": " << flush;
           // cout << solve(i,j,0) << "a " << flush;
          //  cout << solve(i,j,1) << "a " << endl;
            solve(i,j,0);
            solve(i,j,1);
        }
    }
    int mx = 0;
    int mxat = 0;
    srand(907430907);
    for(int i = 0; i < n; i++) {
        for(int j : graph[i]) {
            if(solve(i,j,1)+1 > mx) {
                mx = solve(i,j,1)+1;
                mxat = i+1;
            }
            if(solve(j,i,0)+1 > mx) {
                mx = solve(j,i,0)+1;
                mxat = i+1;
            }
        }
    }
    int wass = mx;
    if(typ == 1) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                ans[j] = -1000;
                was[j] = false;
                with[j] = -1000;
            }
            for(int j : graph[i]) {
                if(check(i,j)+3 > mx) {
                    mxat = with[j]+1;
                    mx = check(i,j)+3;
                }
            }
            for(int j = 0; j < n; j++) {
                ans[j] = -1000;
                was[j] = false;
                with[j] = -1000;
            }
            for(int j : graph[i]) {
                if(check2(i,j)+3 == wass+1) {
                    mxat = with[j]+1;
                    mx = check2(i,j)+3;
                }
            }
        }
        if(mxat < 0 || mx > wass+1) {
            exit(-1);
        }
    }
    cout << mx << "\n" << mxat << "\n";
    return 0;
}

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Runtime error	3 ms	512 KB	Execution failed because the return code was nonzero
3	Correct	2 ms	512 KB	Output is correct
4	Correct	3 ms	640 KB	Output is correct
5	Correct	3 ms	640 KB	Output is correct
6	Correct	5 ms	640 KB	Output is correct
7	Correct	6 ms	768 KB	Output is correct
8	Correct	5 ms	768 KB	Output is correct
9	Correct	7 ms	868 KB	Output is correct
10	Correct	15 ms	1152 KB	Output is correct
11	Correct	9 ms	1024 KB	Output is correct
12	Correct	55 ms	1656 KB	Output is correct
13	Correct	101 ms	2196 KB	Output is correct
14	Correct	82 ms	2660 KB	Output is correct
15	Correct	595 ms	3456 KB	Output is correct
16	Correct	728 ms	3700 KB	Output is correct
17	Incorrect	623 ms	3592 KB	Output isn't correct
18	Correct	111 ms	3072 KB	Output is correct
19	Correct	910 ms	3652 KB	Output is correct
20	Correct	964 ms	3576 KB	Output is correct