Submission #1155920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155920		AmirMakaM	Dreaming (IOI13_dreaming)	C++20	100 / 100	55 ms	24904 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define ull unsigned long long
#define ll long long
#define ld long double
#define pb push_back
#define f first
#define s second 
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define pii pair<int,int> 
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define pdd pair<double,double>
#define mp make_pair   
#define AmirMakaM ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
//#define int long long
// solve it
const ull SEED = chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 mrand(SEED);
ull rnd(ull x = ~(0ull)) {return mrand() % x;} 
const ll MOD = 998244353;
const ll INF = 1e16+20;
const int inf = 1e9 + 7;
const ll N = 1e5+1;
const ll M = 2e3+1;
const double pi = 2*acos(0.0);
const int dx[] = {1,-1,0,0}, dy[] = {0,0,1,-1};

int dp[2][N], mx, res;
vector<pii> g[N];
bool used[N];

void calc(int v) {
    used[v] = 1;
    dp[0][v] = dp[1][v] = 0;
    int mx1 = 0, mx2 = 0;
    for(pii it:g[v]) {
        if(used[it.f]) continue;
        calc(it.f);
        if(dp[0][it.f]+it.s > mx2) mx1 = mx2, mx2 = dp[0][it.f]+it.s;
        else if(dp[0][it.f]+it.s > mx1) mx1 = dp[0][it.f]+it.s;
        dp[0][v] = max(dp[0][it.f]+it.s,dp[0][v]);
    }
    res = max(res,mx1+mx2);
}

void dfs(int v, int pr = -1) {
    vector<pair<int,pii>> t;
    for(pii it:g[v]) {
        if(pr == it.f) continue;
        t.pb({dp[0][it.f]+it.s,{it.f,it.s}});
    }

    t.pb({0,{0,0}});
    sort(all(t));
    mx = min(mx,max(dp[1][v],dp[0][v]));
    for(int i=1; i<sz(t); i++) {
        if(i<sz(t)-1) {
            dp[1][t[i].s.f] = max(t.back().f,dp[1][v]) + t[i].s.s; 
        } else {
            dp[1][t[i].s.f] = max(t[i-1].f,dp[1][v]) + t[i].s.s;
        }
    }

    for(pii it:g[v]) {
        if(pr == it.f) continue;
        dfs(it.f,v);
    }
}

int travelTime(int n,int m,int l,int A[], int B[],int T[]) {
    for(int i=0; i<m; i++) {
        g[A[i]+1].pb({B[i]+1,T[i]});
        g[B[i]+1].pb({A[i]+1,T[i]});
    }

    vector<int> ans;
    for(int i=1; i<=n; i++) used[i] = 0;

    res = 0;
    for(int i=1; i<=n; i++) {
        if(used[i]) continue;
        calc(i);
        mx = inf;
        dfs(i);
        ans.pb(mx);
    }
    sort(all(ans));
    
    if(n-2 == m) {
        res = max(res,ans.back()+ans[sz(ans)-2]+l);
    } else if(n-1-m>1) {
        int t = inf;
        for(int i=0; i<=n-1-m; i++) {
            int l1, l2;
            if(i == n-1-m) l1 = n-2-m, l2 = n-3-m;
            else if(i == n-2-m) l1 = n-1-m, l2 = n-3-m;
            else l1 = n-1-m, l2 = n-2-m;

            t = min(t,max(ans[l1]+ans[l2]+2*l,ans[l1]+ans[i]+l));
        }
        res = max(res,t);
    }
    return res;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23