Submission #94522

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
94522	2019-01-19T19:35:56 Z	nikolapesic2802	Sailing Race (CEOI12_race)	C++14	Compilation error	0 ms	0 KB

race

#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;
}

Compilation message

race.cpp:106:39: error: redefinition of 'template<class T1, class T2> std::ostream& operator<<(std::ostream&, const std::pair<_T1, _T2>&)'
 template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
                                       ^~~~~~~~
race.cpp:20:39: note: 'template<class T1, class T2> std::ostream& operator<<(std::ostream&, const std::pair<_T1, _T2>&)' previously declared here
 template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
                                       ^~~~~~~~
race.cpp:107:28: error: redefinition of 'template<class T> std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)'
 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;}
                            ^~~~~~~~
race.cpp:21:28: note: 'template<class T> std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)' previously declared here
 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;}
                            ^~~~~~~~
race.cpp:108:28: error: redefinition of 'template<class T> std::ostream& operator<<(std::ostream&, const std::set<T>&)'
 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;}
                            ^~~~~~~~
race.cpp:22:28: note: 'template<class T> std::ostream& operator<<(std::ostream&, const std::set<T>&)' previously declared here
 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;}
                            ^~~~~~~~
race.cpp:109:28: error: redefinition of 'template<class T> std::ostream& operator<<(std::ostream&, const std::multiset<T>&)'
 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;}
                            ^~~~~~~~
race.cpp:23:28: note: 'template<class T> std::ostream& operator<<(std::ostream&, const std::multiset<T>&)' previously declared here
 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;}
                            ^~~~~~~~
race.cpp:110:38: error: redefinition of 'template<class T1, class T2> std::ostream& operator<<(std::ostream&, const std::map<T1, T2>&)'
 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;}
                                      ^~~~~~~~
race.cpp:24:38: note: 'template<class T1, class T2> std::ostream& operator<<(std::ostream&, const std::map<T1, T2>&)' previously declared here
 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;}
                                      ^~~~~~~~
race.cpp:111:11: error: redefinition of 'const int N'
 const int N=501;
           ^
race.cpp:25:11: note: 'const int N' previously defined here
 const int N=501;
           ^
race.cpp:112:14: error: redefinition of 'bool adj [501][501]'
 bool adj[N][N];
              ^
race.cpp:26:6: note: 'bool adj [501][501]' previously declared here
 bool adj[N][N];
      ^~~
race.cpp:113:16: error: redefinition of 'int dp1 [501][501][2]'
 int dp1[N][N][2],dp2[N][N][2],dp3[N][N][2],b[N][2];
                ^
race.cpp:27:5: note: 'int dp1 [501][501][2]' previously declared here
 int dp1[N][N][2],dp2[N][N][2],dp3[N][N][2],b[N][2];
     ^~~
race.cpp:113:29: error: redefinition of 'int dp2 [501][501][2]'
 int dp1[N][N][2],dp2[N][N][2],dp3[N][N][2],b[N][2];
                             ^
race.cpp:27:18: note: 'int dp2 [501][501][2]' previously declared here
 int dp1[N][N][2],dp2[N][N][2],dp3[N][N][2],b[N][2];
                  ^~~
race.cpp:113:42: error: redefinition of 'int dp3 [501][501][2]'
 int dp1[N][N][2],dp2[N][N][2],dp3[N][N][2],b[N][2];
                                          ^
race.cpp:27:31: note: 'int dp3 [501][501][2]' previously declared here
 int dp1[N][N][2],dp2[N][N][2],dp3[N][N][2],b[N][2];
                               ^~~
race.cpp:113:50: error: redefinition of 'int b [501][2]'
 int dp1[N][N][2],dp2[N][N][2],dp3[N][N][2],b[N][2];
                                                  ^
race.cpp:27:44: note: 'int b [501][2]' previously declared here
 int dp1[N][N][2],dp2[N][N][2],dp3[N][N][2],b[N][2];
                                            ^
race.cpp:114:15: error: redefinition of 'std::pair<int, int> ans'
 pair<int,int> ans;
               ^~~
race.cpp:28:15: note: 'std::pair<int, int> ans' previously defined here
 pair<int,int> ans;
               ^~~
race.cpp: In function 'void calc(int, int, int)':
race.cpp:115:6: error: redefinition of 'void calc(int, int, int)'
 void calc(int l,int r,int a)
      ^~~~
race.cpp:29:6: note: 'void calc(int, int, int)' previously defined here
 void calc(int l,int r,int a)
      ^~~~
race.cpp: In function 'int main()':
race.cpp:130:5: error: redefinition of 'int main()'
 int main()
     ^~~~
race.cpp:44:5: note: 'int main()' previously defined here
 int main()
     ^~~~
race.cpp: In function 'int main()':
race.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
race.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&t);
         ~~~~~^~~~~~~~~
race.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&t);
             ~~~~~^~~~~~~~~
race.cpp: In function 'int main()':
race.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
race.cpp:137:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&t);
         ~~~~~^~~~~~~~~
race.cpp:141:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i",&t);
             ~~~~~^~~~~~~~~