Submission #240661

#	Time	Username	Problem	Language	Result	Execution time	Memory
240661		Coroian_David	Dreaming (IOI13_dreaming)	C++11	100 / 100	156 ms	32504 KiB

dreaming

#include <bits/stdc++.h>

#include "dreaming.h"

#define MAX_N 100000

#define xx first
#define yy second

using namespace std;

const int sqrInf = (int)(1e9);

vector <pair<int, int>> g[MAX_N + 1];

void add(int a, int b, int c)
{
    g[a].push_back({b, c});
}

int k;
int mn;
int dist[MAX_N + 1];
int dp[MAX_N + 1];

int st[MAX_N + 1];
int dr[MAX_N + 1 + 1];
int nod[MAX_N + 1];
int dst[MAX_N + 1];
int xxa[MAX_N + 1];

int viz[MAX_N + 1];

int n;

void dfs(int a)
{
    viz[a] = 1;
    for(auto u : g[a])
    {
        if(viz[u.xx] == 0)
        {
            dfs(u.xx);
            dp[a] = max(dp[a], u.yy + dp[u.xx]);
        }
    }
}

int rez;

void dfsDist(int a, int tata, int d)
{
    int w = max(d, dp[a]);
    mn = min(mn, w);

    vector <int> t2;
    t2.clear();

    int x = 0;
    for(auto u : g[a])
    {
        if(u.xx != tata)
        {
            t2.push_back(u.xx);
            nod[++ x] = u.xx;
            dst[x] = u.yy;
            xxa[x] = dp[u.xx] + u.yy;
        }
    }

    st[1] = xxa[1];
    for(int i = 2; i <= x; i ++)
        st[i] = max(st[i - 1], xxa[i]);

    dr[x] = xxa[x];
    for(int i = x - 1; i >= 1; i --)
        dr[i] = max(dr[i + 1], xxa[i]);

    vector <int> tmp;
    tmp.clear();

    st[0] = dr[x + 1] = 0;
    for(int i = 1; i <= x; i ++)
        tmp.push_back(max({d, st[i - 1], dr[i + 1]}) + dst[i]);

    sort(xxa + 1, xxa + x + 1);
    if(x > 1)
        rez = max(rez, xxa[x] + xxa[x - 1]);\
    rez = max(rez, dp[a] + d);

    int i = 0;
    for(auto u : t2)
    {
        i ++;
        dfsDist(u, a, tmp[i - 1]);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    n = N;
    for(int i = 0; i < M; i ++)
    {
        int a = A[i] + 1;
        int b = B[i] + 1;
        add(a, b, T[i]);
        add(b, a, T[i]);
    }

    for(int i = 1; i <= n; i ++)
    {
        if(viz[i] == 0)
        {
            dfs(i);

           // cout << " AVEM COMP " << i << " " << dp[i] << "\n";

            mn = sqrInf;
            dfsDist(i, -1, 0);
            dist[++ k] = mn;

         //   cout << "ACEASTA COMP ARE DISTR MAX  " << dist[k] << "\n";
        }
    }

    sort(dist + 1, dist + k + 1);

   // cout << rez << " " << dist[k] << " " << dist[k - 1] << " " << dist[k - 2] << "\n";

    return max(rez, (k == 1 ? dist[k] :
                    (k == 2 ? dist[k] + dist[k - 1] + L : max(dist[k] + dist[k - 1] + L, dist[k - 1] + dist[k - 2] + (L << 1)))));
}

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