답안 #94521

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94521 2019-01-19T19:34:50 Z nikolapesic2802 Sailing Race (CEOI12_race) C++14
25 / 100
1160 ms 6520 KB
#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 a=0;a<2;a++)
            ans=max(ans,make_pair(dp3[i][b[i][a^1]][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: 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);
             ~~~~~^~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 508 KB Output isn't correct
2 Incorrect 2 ms 632 KB Output isn't correct
3 Incorrect 2 ms 760 KB Output isn't correct
4 Incorrect 3 ms 888 KB Output isn't correct
5 Correct 3 ms 1016 KB Output is correct
6 Incorrect 4 ms 1016 KB Output isn't correct
7 Correct 4 ms 1148 KB Output is correct
8 Incorrect 6 ms 1272 KB Output isn't correct
9 Correct 6 ms 1400 KB Output is correct
10 Correct 7 ms 1528 KB Output is correct
11 Correct 7 ms 1528 KB Output is correct
12 Incorrect 72 ms 2808 KB Output isn't correct
13 Incorrect 208 ms 4088 KB Output isn't correct
14 Incorrect 279 ms 5280 KB Output isn't correct
15 Incorrect 1061 ms 6392 KB Output isn't correct
16 Incorrect 1087 ms 6520 KB Output isn't correct
17 Incorrect 1035 ms 6500 KB Output isn't correct
18 Incorrect 522 ms 6504 KB Output isn't correct
19 Incorrect 1127 ms 6520 KB Output isn't correct
20 Incorrect 1160 ms 6396 KB Output isn't correct