답안 #94523

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94523 2019-01-19T19:36:28 Z nikolapesic2802 Sailing Race (CEOI12_race) C++14
25 / 100
1145 ms 6524 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][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 504 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 1148 KB Output isn't correct
7 Correct 4 ms 1116 KB Output is correct
8 Incorrect 6 ms 1400 KB Output isn't correct
9 Correct 5 ms 1480 KB Output is correct
10 Correct 7 ms 1528 KB Output is correct
11 Correct 6 ms 1528 KB Output is correct
12 Incorrect 70 ms 2808 KB Output isn't correct
13 Incorrect 207 ms 3960 KB Output isn't correct
14 Incorrect 262 ms 5280 KB Output isn't correct
15 Incorrect 995 ms 6520 KB Output isn't correct
16 Incorrect 1078 ms 6520 KB Output isn't correct
17 Incorrect 1014 ms 6524 KB Output isn't correct
18 Incorrect 548 ms 6392 KB Output isn't correct
19 Incorrect 1134 ms 6520 KB Output isn't correct
20 Incorrect 1145 ms 6496 KB Output isn't correct