| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 94522 | nikolapesic2802 | Sailing Race (CEOI12_race) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
const int N=501;
bool adj[N][N];
int dp1[N][N][2],dp2[N][N][2],dp3[N][N][2],b[N][2];
pair<int,int> ans;
void calc(int l,int r,int a)
{
if(adj[l][r])
{
dp1[l][r][a]=1;
dp2[l][r][a]=1+dp3[r][b[l][a]][a^1];
}
else
{
dp1[l][r][a]=dp2[l][r][a]=INT_MIN;
}
for(int k=b[l][a];k!=r;k=b[k][a])
dp1[l][r][a]=max(dp1[l][r][a],dp1[l][k][a]+dp1[k][r][a]),dp2[l][r][a]=max(dp2[l][r][a],dp1[l][k][a]+dp2[k][r][a]);
dp3[l][r][a]=max(dp3[l][b[r][a^1]][a],dp2[l][r][a]);
}
int main()
{
int n,k;
scanf("%i %i",&n,&k);
for(int i=0;i<n;i++)
{
int t;
scanf("%i",&t);
while(t!=0)
{
adj[i][t-1]=true;
scanf("%i",&t);
}
b[i][0]=(i+1)%n;
b[i][1]=(i-1+n)%n;
}
for(int l=1;l<n;l++)
for(int i=0;i<n;i++)
calc(i,(i+l)%n,0),calc((i+l)%n,i,1);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int a=0;a<2;a++)
ans=max(ans,make_pair(dp2[i][j][a],i));
if(k)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int a=0;a<2;a++)
if(dp1[i][j][a]>0)
{
int k=b[j][a];
for(;k!=i;k=b[k][a])
if(adj[k][i])
break;
if(k!=i)
for(int l=b[k][a];l!=i;l=b[l][a])
if(adj[j][l])
ans=max(ans,make_pair(max(dp3[l][b[i][a^1]][a],dp3[l][b[k][a]][a^1])+dp1[i][j][k]+2,k));
}
}
printf("%i\n%i\n",ans.first,ans.second+1);
return 0;
}
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
const int N=501;
bool adj[N][N];
int dp1[N][N][2],dp2[N][N][2],dp3[N][N][2],b[N][2];
pair<int,int> ans;
void calc(int l,int r,int a)
{
if(adj[l][r])
{
dp1[l][r][a]=1;
dp2[l][r][a]=1+dp3[r][b[l][a]][a^1];
}
else
{
dp1[l][r][a]=dp2[l][r][a]=INT_MIN;
}
for(int k=b[l][a];k!=r;k=b[k][a])
dp1[l][r][a]=max(dp1[l][r][a],dp1[l][k][a]+dp1[k][r][a]),dp2[l][r][a]=max(dp2[l][r][a],dp1[l][k][a]+dp2[k][r][a]);
dp3[l][r][a]=max(dp3[l][b[r][a^1]][a],dp2[l][r][a]);
}
int main()
{
int n,k;
scanf("%i %i",&n,&k);
for(int i=0;i<n;i++)
{
int t;
scanf("%i",&t);
while(t!=0)
{
adj[i][t-1]=true;
scanf("%i",&t);
}
b[i][0]=(i+1)%n;
b[i][1]=(i-1+n)%n;
}
for(int l=1;l<n;l++)
for(int i=0;i<n;i++)
calc(i,(i+l)%n,0),calc((i+l)%n,i,1);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int a=0;a<2;a++)
ans=max(ans,make_pair(dp2[i][j][a],i));
if(k)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int a=0;a<2;a++)
if(dp1[i][j][a]>0)
{
int k=b[j][a];
for(;k!=i;k=b[k][a])
if(adj[k][i])
break;
if(k!=i)
for(int l=b[k][a];l!=i;l=b[l][a])
if(adj[j][l])
ans=max(ans,make_pair(max(dp3[l][b[i][a^1]][a],dp3[l][b[k][a]][a^1])+dp1[i][j][k]+2,k));
}
}
printf("%i\n%i\n",ans.first,ans.second+1);
return 0;
}