Submission #115110

#	Time	Username	Problem	Language	Result	Execution time	Memory
115110		bazsi700	Sailing Race (CEOI12_race)	C++14	90 / 100	964 ms	3700 KiB

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 / 100