Submission #383679

#	Time	Username	Problem	Language	Result	Execution time	Memory
383679		davooddkareshki	Dreaming (IOI13_dreaming)	C++17	100 / 100	105 ms	17556 KiB

dreaming

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

typedef long long ll;
typedef long double ld;

using namespace std;

///#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

const ll inf = 2e9;
const int maxn = 1e5+10;
const int mod = 1e9+7;

vector<pii> g[maxn];
bool mark[maxn];
vector<int> fel;
int par[maxn], V;
int down[maxn], up[maxn], ANS = 0;

void dfs(int v)
{
    mark[v] = 1;

    int MX = 0;
    for(auto e : g[v])
    {
        int u = e.F, w = e.S;
        if(u != par[v])
        {
            par[u] = v;
            dfs(u);
            down[v] = max(down[u]+w, down[v]);
            up[u] = max(up[u], MX + w);
            MX = max(MX, down[u]+w);
        }
    }

    MX = 0;
    reverse(g[v].begin(), g[v].end());
    for(auto e : g[v])
    {
        int u = e.F, w = e.S;
        if(u != par[v])
        {
            up[u] = max(up[u], MX + w);
            MX = max(MX, down[u]+w);
        }
    }
    reverse(g[v].begin(), g[v].end());
}

int MN = inf;
void lfs(int v)
{
    for(auto e : g[v])
    {
        int u = e.F, w = e.S;
        if(u != par[v])
        {
            up[u] = max(up[u], up[v] + w);
            lfs(u);
        }
    }

    //cout<< v <<" "<< down[v] <<" "<< up[v] <<"\n";

    int door = max(up[v], down[v]);
    ANS = max(ANS,door);
    MN = min(MN, door);
}

/*int A[8] = {0, 8, 2, 5, 5, 1, 1, 10};
int B[8] = {8, 2, 7, 11, 1, 3, 9, 6};
int T[8] = {4, 2, 4, 3, 7, 1, 5, 3};*/
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    for(int i = 0; i < M; i++)
    {
        g[A[i]].push_back({B[i],T[i]});
        g[B[i]].push_back({A[i],T[i]});
    }

    for(int v = 0; v < N; v++)
        if(!mark[v])
        {
            MN = inf;
            dfs(v); lfs(v);
            fel.push_back(MN);
            //cout<< MN <<" ";
        }

    sort(fel.begin(), fel.end());
    if((int)fel.size() == 1) return ANS;
    if((int)fel.size() == 2) return max(fel[0] + fel[1] + L, ANS);

    //cout<< ANS <<" ";
    int MM = (int)fel.size();
    return max({fel[MM-1] + fel[MM-2] + L, fel[MM-2] + fel[MM-3] + 2 * L, ANS});
}/*

signed main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout<< travelTime(12, 8, 2);
}
*/

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