Submission #66398

#	Time	Username	Problem	Language	Result	Execution time	Memory
66398		ikura355	Sailing Race (CEOI12_race)	C++14	35 / 100	3071 ms	11884 KiB

race

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

const int maxn = 500 + 5;
const int inf = 1e6;

int n,k;
int way[maxn][maxn];
vector<int> yaw[maxn];
int dp[maxn][maxn][2];
int dp2[maxn][maxn][2];
int mx[maxn];
vector<pair<pair<int,int>,int>> a[maxn];

int add(int x, int y) {
	return ((x+y)%n + n)%n;
}

int f(int x, int y, int t) {
    return dp[x][y][t];
}

int g(int x, int y, int t) {
    return dp2[x][y][t];
}

void init() {
    for(int u=0;u<n;u++) {
        for(int v=0;v<n;v++) {
            a[add(v,-u)].push_back({{u,v},0});
            a[add(u,-v)].push_back({{u,v},1});
        }
    }
    for(int sz=0;sz<n;sz++) {
        for(auto tt : a[sz]) {
            int u = tt.first.first, v = tt.first.second, t = tt.second;
            dp2[u][v][t] = -inf;
            if(way[u][v]) dp2[u][v][t] = 1;
            int wow = (t==0 ? 1:-1);
            for(int x=add(u,wow);x!=v;x=add(x,wow)) {
                if(!way[u][x]) continue;
                dp[u][v][t] = max(dp[u][v][t], max(f(x,u,!t), f(x,v,t)) + 1);
                dp2[u][v][t] = max(dp2[u][v][t], g(x,v,t) + 1);
            }
        }
    }
}

int main() {
	scanf("%d%d",&n,&k);
	for(int u=0;u<n;u++) {
		int v;
		while(scanf("%d",&v) && v) {
			--v;
			way[u][v] = 1;
			yaw[v].push_back(u);
		}
	}
	init();
    pair<int,int> res = {-1,-1};
    for(int u=0;u<n;u++) res = max(res, {f(u,u,0), u});
	if(k) {
		for(int u=0;u<n;u++) {
			//case 1
			for(int v=0;v<n;v++) mx[v] = 0;
			for(int v=add(u,1);v!=u;v=add(v,1)) {
				if(way[u][v]) {
					for(int x=add(v,1);x!=u;x=add(x,1)) {
//					    printf("case 1 : u = %d v = %d x = %d => 1 + %d + %d\n",u,v,x,mx[x],g(v,x,0));
						res = max(res, {1 + mx[x] + g(v,x,0), u});
					}
				}
				for(auto x : yaw[v]) mx[x] = max(mx[x], f(v,u,1) + 1);
			}
			//case 2
			for(int v=0;v<n;v++) mx[v] = 0;
			for(int v=add(u,-1);v!=u;v=add(v,-1)) {
				if(way[u][v]) {
					for(int x=add(v,-1);x!=u;x=add(x,-1)) {
//					    printf("case 2 : u = %d v = %d x = %d => 1 + %d + %d\n",u,v,x,mx[x],g(v,x,1));
						res = max(res, {1 + mx[x] + g(v,x,1), u});
					}
				}
				for(auto x : yaw[v]) mx[x] = max(mx[x], f(v,u,0) + 1);
			}
		}
		for(int v=0;v<n;v++) {
			//case 3
			for(int u=0;u<n;u++) mx[u] = 0;
			for(int u=add(v,-1);u!=v;u=add(u,-1)) {
				if(way[u][v]) {
					for(int x=add(v,1);x!=u;x=add(x,1)) {
//					    printf("case 2 : u = %d v = %d x = %d => 1 + %d + %d\n",u,v,x,mx[x],g(v,x,0));
						res = max(res, {1 + mx[x] + g(v,x,0), u});
					}
				}
				for(auto x : yaw[u]) mx[x] = max(mx[x], f(u,v,0) + 1);
			}
			//case 4
			for(int u=0;u<n;u++) mx[u] = 0;
			for(int u=add(v,1);u!=v;u=add(u,1)) {
				if(way[u][v]) {
					for(int x=add(v,-1);x!=u;x=add(x,-1)) {
//					    printf("case 2 : u = %d v = %d x = %d => 1 + %d + %d\n",u,v,x,mx[x],g(v,x,1));
						res = max(res, {1 + mx[x] + g(v,x,1), u});
					}
				}
				for(auto x : yaw[u]) mx[x] = max(mx[x], f(u,v,1) + 1);
			}
		}
 	}
    printf("%d\n%d",res.first,res.second+1);
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 35 / 100