Submission #260075

#	Time	Username	Problem	Language	Result	Execution time	Memory
260075		SamAnd	Dreaming (IOI13_dreaming)	C++17	100 / 100	99 ms	16888 KiB

dreaming

#include "dreaming.h"
//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 100005, INF = 1000000009;

int ans;

int n;
vector<pair<int, int> > g[N];

bool c[N];

int dp[N];
void dfs0(int x, int p)
{
    c[x] = true;
    dp[x] = 0;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        if (h == p)
            continue;
        dfs0(h, x);
        dp[x] = max(dp[x], dp[h] + g[x][i].se);
    }
}

int minu;
void dfs1(int x, int p, int dpp)
{
    int max1 = 0, max2 = 0;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        if (h == p)
        {
            if (dpp + g[x][i].se >= max1)
            {
                max2 = max1;
                max1 = dpp + g[x][i].se;
            }
            else if (dpp + g[x][i].se >= max2)
                max2 = dpp + g[x][i].se;
            continue;
        }
        if (dp[h] + g[x][i].se >= max1)
        {
            max2 = max1;
            max1 = dp[h] + g[x][i].se;
        }
        else if (dp[h] + g[x][i].se >= max2)
            max2 = dp[h] + g[x][i].se;
    }
    ans = max(ans, max1 + max2);
    minu = min(minu, max1);
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i].fi;
        if (h == p)
            continue;
        if (dp[h] + g[x][i].se == max1)
            dfs1(h, x, max2);
        else
            dfs1(h, x, max1);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    for (int i = 0; i < M; ++i)
    {
        int x = A[i];
        int y = B[i];
        int z = T[i];
        g[x].push_back(m_p(y, z));
        g[y].push_back(m_p(x, z));
    }
    multiset<int> s;
    for (int x = 0; x < N; ++x)
    {
        if (c[x])
            continue;
        dfs0(x, x);
        minu = INF;
        dfs1(x, x, 0);
        s.insert(minu);
    }
    while (sz(s) > 1)
    {
        int x = *s.begin();
        s.erase((s.begin()));
        int y = *(--s.end());
        s.erase((--s.end()));
        ans = max(ans, x + L + y);
        int minu = min(max(x, L + y), max(x + L, y));
        s.insert(minu);
    }
    return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs0(int, int)':
dreaming.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs1(int, int, int)':
dreaming.cpp:38:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
dreaming.cpp:62:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~

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