답안 #94548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94548 2019-01-20T11:02:00 Z nikolapesic2802 Sailing Race (CEOI12_race) C++14
40 / 100
1123 ms 6688 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 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][a]+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 504 KB Output isn't correct
2 Correct 2 ms 632 KB Output is correct
3 Incorrect 2 ms 632 KB Output isn't correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 4 ms 1144 KB Output is correct
7 Correct 5 ms 1144 KB Output is correct
8 Incorrect 6 ms 1276 KB Output isn't correct
9 Correct 6 ms 1528 KB Output is correct
10 Correct 8 ms 1656 KB Output is correct
11 Correct 7 ms 1528 KB Output is correct
12 Incorrect 73 ms 2840 KB Output isn't correct
13 Incorrect 211 ms 4088 KB Output isn't correct
14 Incorrect 279 ms 5240 KB Output isn't correct
15 Incorrect 1032 ms 6644 KB Output isn't correct
16 Incorrect 1052 ms 6624 KB Output isn't correct
17 Incorrect 1040 ms 6520 KB Output isn't correct
18 Incorrect 542 ms 6520 KB Output isn't correct
19 Incorrect 1123 ms 6684 KB Output isn't correct
20 Incorrect 1105 ms 6688 KB Output isn't correct