Submission #362902

# Submission time Handle Problem Language Result Execution time Memory
362902 2021-02-04T16:24:34 Z ACmachine Sailing Race (CEOI12_race) C++17
50 / 100
3000 ms 4460 KB
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<str> vstr;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define rsz resize 
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
	
const double EPS = 1e-9;
const int MOD = 1e9+7; // 998244353;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

#ifdef DEBUG
#define DBG if(1)
#else
#define DBG if(0)
#endif

#define dbg(x) cout << "(" << #x << " : " << x << ")" << endl;
// ostreams
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }
//searches
template<typename T, typename U>
T bsl(T lo, T hi, U f){ hi++; T mid; while(lo < hi){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; }
template<typename U>
double bsld(double lo, double hi, U f, double p = 1e-9){ int r = 3 + (int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid; } return (lo + hi)/2; }
template<typename T, typename U>
T bsh(T lo, T hi, U f){ lo--; T mid; while(lo < hi){ mid = (lo + hi + 1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; }
template<typename U>
double bshd(double lo, double hi, U f, double p = 1e-9){ int r = 3+(int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? lo = mid : hi = mid; } return (lo + hi)/2; }
// some more utility functions
template<typename T>
pair<T, int> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return mp(*it, it - v.begin());}
template<typename T>
pair<T, int> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return mp(*it, it - v.begin());}        
template<typename T> bool ckmin(T& a, const T& b){return b < a ? a = b , true : false;}
template<typename T> bool ckmax(T& a, const T& b){return b > a ? a = b, true : false;}

    
int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
	int n, T; cin >> n >> T;
    vector<vector<array<int, 2>>> dp(n, vector<array<int, 2>>(n, {0, 0}));
    vector<vector<bool>> mat(n, vector<bool>(n, false));
    REP(i, n){
        int x; cin >> x;
        while(x != 0){
            x--; 
            mat[i][x] = true;
            cin >> x;
        }
    }
    // dp[i][j][d] -> som na i, obluk mozem kratcat j dopredu / dozadu podla d
    auto calc_dp = [&](){
        REP(i, n){
            dp[i][0][0] = dp[i][0][1] = 0;
        }
        FOR(ln, 1, n, 1){
            REP(i, n){
                FOR(k, 1, ln + 1, 1){
                    int nxt = (i + k) % n;
                    if(!mat[i][nxt]) continue;
                    dp[i][ln][0] = max(dp[i][ln][0], 1 + dp[nxt][k - 1][1]);
                    dp[i][ln][0] = max(dp[i][ln][0], 1 + dp[nxt][ln - k][0]);
                }
                FOR(k, 1, ln + 1, 1){
                    int nxt = (i - k);
                    if(nxt < 0) nxt += n;
                    if(!mat[i][nxt]) continue;
                    dp[i][ln][1] = max(dp[i][ln][1], 1 + dp[nxt][k - 1][0]);
                    dp[i][ln][1] = max(dp[i][ln][1], 1 + dp[nxt][ln - k][1]);
                }
            }
        }
    };
    calc_dp();
    int maxs_without_intersection = 0;
    REP(i, n){
        if(dp[i][n - 1][0] > dp[maxs_without_intersection][n - 1][0])
            maxs_without_intersection = i;
    }
    if(T == 0){
        cout << dp[maxs_without_intersection][n - 1][0] << "\n";
        cout << maxs_without_intersection + 1 << "\n";
        return 0;
    }
    // ak chcem len raz intersectnut prvy tah;
    // spravim prvy tah, dostanem 2 obluky; v jednom obluku musim robit zatacky len rovnakym smerom; potom skocim na druhy obluk a transitionujem do hornej dp tabulky; 
    // dp_t[i][j][0] -> maximalny pocet tahov jednym smerom ak sa musim posunut presne o j krokov do smeru; -1 ak sa neda
    vector<vector<array<int, 2>>> dp_t(n, vector<array<int, 2>>(n, {-1, -1})); 
    auto calc_dpt = [&](){
        REP(i, n){
            dp_t[i][0][0] = dp_t[i][0][1] = 0;
            FOR(k, 1, n, 1){
                int nxt = (i + k) % n;
                if(mat[i][nxt])
                    dp_t[i][k][0] = 1;
                int nxt2 = (i - k);
                if(nxt2 < 0) nxt2 += n;
                if(mat[i][nxt2])
                    dp_t[i][k][1] = 1;
            }
        }
        FOR(ln, 1, n, 1){
            REP(i, n){
                FOR(k, 1, ln + 1, 1){
                    int nxt = (i + k) % n;
                    if(dp_t[i][k][0] == -1) continue;
                    if(dp_t[nxt][ln - k][0] != -1)
                        dp_t[i][ln][0] = max(dp_t[i][ln][0], dp_t[i][k][0] + dp_t[nxt][ln - k][0]);
                }
                FOR(k, 1, ln + 1, 1){
                    int nxt = i - k;
                    if(nxt < 0) nxt += n;
                    if(dp_t[i][k][1] == -1) continue;
                    if(dp_t[nxt][ln - k][1] != -1)
                        dp_t[i][ln][1] = max(dp_t[i][ln][1], dp_t[i][k][1] + dp_t[nxt][ln - k][1]);
                }
            }
        }
    };
    calc_dpt();
    // spajam tie obluky; bruteforce zaciatocneho pristavu, bruteforce prveho tahu, bruteforce druheho tahu, bruteforce 3 tahu -> O(n^4);
    // ak zmazeme bruteforce 2 tahu, dostneme sa na O(n^3);
    // druhy tah pozostava z viacerych tahov jednym smerom -> dpt; po 3 zvysok je zaciatocne dp; 
    
    int maxs_intersection = 0;
    int maxs_intersection_value = 0;
    REP(i, n){
        FOR(k, 1, n, 1){ // clockwise prve tahy ->tahy jednym smerom
            int d1 = (i + k) % n; 
            FOR(g, 1, (n - 1) - k + 1, 1){ // pokracujem clockwise
                int d2 = (d1 + g) % n;
                FOR(l, 1, k, 1){
                    int d3 = (i + l) % n; // volne z prveho tahu
                    if(!mat[d2][d3]) continue;
                    if(dp_t[d1][g][0] == -1) continue;
                    int re = 1 + dp_t[d1][g][0] + 1 + max(dp[d3][k - l - 1][0], dp[d3][l - 1][1]);
                    if(re > maxs_intersection_value){
                        maxs_intersection_value = re;
                        maxs_intersection = i;
                    }
                }
            }
        }
        FOR(k, 1, n, 1){ // counterclockwise tahy;
            int d1 = (i - k);
            if(d1 < 0) d1 += n;
            FOR(g, 1, (n - 1) - k + 1, 1){
                int d2 = (d1 - g);
                if(d2 < 0) d2 += n;
                FOR(l, 1, k, 1){
                    int d3 = (i - l);
                    if(d3 < 0) d3 += n;
                    if(!mat[d2][d3]) continue;
                    if(dp_t[d1][g][1] == -1) continue;
                    int re = 1 + dp_t[d1][g][1] + 1 + max(dp[d3][k - l - 1][1], dp[d3][l - 1][0]);
                    if(re > maxs_intersection_value){
                        maxs_intersection_value = re;
                        maxs_intersection = i;
                    }
                }
            }
        }
    }
    if(maxs_intersection_value > dp[maxs_without_intersection][n - 1][0]){
        cout << maxs_intersection_value << "\n";
        cout << maxs_intersection + 1 << "\n";
    }
    else{
        cout << dp[maxs_without_intersection][n - 1][0] << "\n";
        cout << maxs_without_intersection + 1 << "\n";
    }
    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 3 ms 364 KB Output isn't correct
4 Correct 7 ms 364 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Incorrect 30 ms 364 KB Output isn't correct
7 Correct 3 ms 384 KB Output is correct
8 Incorrect 75 ms 492 KB Output isn't correct
9 Correct 7 ms 492 KB Output is correct
10 Correct 7 ms 364 KB Output is correct
11 Correct 9 ms 364 KB Output is correct
12 Incorrect 2851 ms 1056 KB Output isn't correct
13 Execution timed out 3068 ms 1772 KB Time limit exceeded
14 Correct 292 ms 1704 KB Output is correct
15 Execution timed out 3076 ms 4460 KB Time limit exceeded
16 Execution timed out 3081 ms 4460 KB Time limit exceeded
17 Execution timed out 3081 ms 4460 KB Time limit exceeded
18 Correct 513 ms 2412 KB Output is correct
19 Execution timed out 3033 ms 4460 KB Time limit exceeded
20 Execution timed out 3043 ms 4348 KB Time limit exceeded