Submission #1166020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166020		Boycl07	Dreaming (IOI13_dreaming)	C++20	100 / 100	69 ms	18192 KiB

dreaming

#include"dreaming.h"
#include "bits/stdc++.h"

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 1; i <= (n); ++i)
#define forn(i, l, r) for(int i = (l); (i) <= (r); ++i)
#define ford(i, r, l) for(int i = (r); (i) >= (l); --i)
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define task "note"

template<typename T> bool maximize(T &res, const T &val) {if(res < val) {res = val; return 1;} return 0;}
template<typename T> bool minimize(T &res, const T &val) {if(res < val) return 0; res = val; return 1;}
inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}

const int N = 2e5 + 3;
const int LOG = 23;
const int INF = 1e9 + 3;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double get_cur_time() {return chrono::steady_clock::now().time_since_epoch().count();}
double TIMELM = 1000 - 100;
const int MOD = 1e9 + 7;

int n, m, l;
vector<pii> g[N];
int best;
int res = 0;

pii dp[N];
void add(pii &x, int y)
{
    if(x.fi < y) x.se = x.fi, x.fi = y;
    else maximize(x.se, y);
}
void sub(pii &x, int y)
{
    if(x.fi == y) x.fi = x.se, x.se = 0;
}
bool vis[N];
void dfs(int u, int p)
{
    dp[u] = {0, 0};
    vis[u] = 1;
    for(auto &[v, w] : g[u]) if(v != p)
    {
        dfs(v, u);
        add(dp[u], dp[v].fi + w);
    }
}
void change(int u, int v, int w)
{
    sub(dp[u], dp[v].fi + w);
    add(dp[v], dp[u].fi + w);
}
void dfs_reroot(int u, int p)
{
    minimize(best, dp[u].fi);
    maximize(res, dp[u].fi);
    for(auto &[v, w] : g[u]) if(v != p)
    {
        change(u, v, w);
        dfs_reroot(v, u);
        change(v, u, w);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int C[])
{
    n = N, m = M;
    rep(i, m)
    {
        int u = A[i - 1], v = B[i - 1], w = C[i - 1];
        ++u;
        ++v;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    priority_queue<int> cen;
    rep(i, n) if(!vis[i])
    {
        best = INF;
        dfs(i, i);
        dfs_reroot(i, i);
        cen.push(best);
    }
    while(sz(cen) > 1)
    {
        int d1 = cen.top(); cen.pop();
        int d2 = cen.top(); cen.pop();
        maximize(res, d1 + d2 + L);
        int new_d = min(max(d1, d2 + L), max(d1 + L, d2));
        cen.push(new_d);
    }

    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