Submission #383643

#	Time	Username	Problem	Language	Result	Execution time	Memory
383643		davooddkareshki	Dreaming (IOI13_dreaming)	C++17	18 / 100	47 ms	11756 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 int inf = 1e9;
const int maxn = 1e5+10;
const int mod = 1e9+7;

vector<pii> g[maxn];
bool mark[maxn];
vector<int> fel;
int par[maxn], h[maxn], V;

void dfs(int v)
{
    if(h[v] > h[V]) V = v;

    mark[v] = 1;
    for(auto e : g[v])
    {
        int u = e.F, w = e.S;
        if(u != par[v])
        {
            par[u] = v;
            h[u] = h[v] + w;
            dfs(u);
        }
    }
}

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])
        {
            V = v;
            dfs(v);
            int X = V;
            dfs(X);

            int Y = V;
            int ans = h[Y];
            while(V != X)
            {
                ans = min(ans, max(h[Y]-h[V],h[V]));
                V = par[V];
            }
            fel.push_back(ans);
        }

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

    int MM = (int)fel.size();
    return max(fel[MM-1] + fel[MM-2] + L, fel[MM-2] + fel[MM-3] + 2 * L);
}

/*
signed main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cout<< travelTime(12, 8, 2,
                    {0, 8, 2, 5, 5, 1, 1, 10},
                    {8, 2, 7, 11, 1, 3, 9, 6},
                    {4, 2, 4, 3, 7, 1, 5, 3});
}
*/

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