Submission #842911

#	Time	Username	Problem	Language	Result	Execution time	Memory
842911		12345678	Dreaming (IOI13_dreaming)	C++17	47 / 100	66 ms	30968 KiB

dreaming

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

using namespace std;

const int nx=1e5+5;
int mx[nx], mxr[nx], nxt, mx1=INT_MAX, mx2=INT_MAX, ans;
bool vs[nx];
vector<vector<pair<int, int>>> d(nx);

void dfs(int u, int p)
{
    vs[u]=1;
    for (auto [v, w]:d[u])
    {
        if (v==p) continue;
        dfs(v, u);
        mx[u]=max(mx[u], mx[v]+w);
    }
}

void dfs2(int u, int p)
{
    vector<int> pf(d[u].size()+2), sf(d[u].size()+2);
    pf[0]=mxr[u];
    for (int i=d[u].size()-1; i>=0; i--)
    {
        sf[i+1]=sf[i+2];
        if (d[u][i].first==p) continue;
        sf[i+1]=max(sf[i+1], d[u][i].second+mx[d[u][i].first]);
    }
    for (int i=0; i<d[u].size(); i++)
    {
        pf[i+1]=pf[i];
        if (d[u][i].first==p) continue;
        pf[i+1]=max(pf[i+1], d[u][i].second+mx[d[u][i].first]);
        mxr[d[u][i].first]=max(pf[i], sf[i+2])+d[u][i].second;
    }
    for (auto [v, w]:d[u]) if (v!=p) dfs2(v, u);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i=0; i<M; i++) d[A[i]].push_back({B[i], T[i]}), d[B[i]].push_back({A[i], T[i]});
    dfs(0, 0); dfs2(0, 0);
    for (int i=0; i<N; i++)
    {
        if (!vs[i]) nxt=i;
        else vs[i]=0, mx1=min(mx1, max(mx[i], mxr[i]));
    }
    dfs(nxt, nxt); dfs2(nxt, nxt);
    for (int i=0; i<N; i++) if (vs[i]) mx2=min(mx2, max(mx[i], mxr[i]));
    for (int i=0; i<N; i++) ans=max(ans, mx[i]+mxr[i]);
    return max(ans, mx1+mx2+L);
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i=0; i<d[u].size(); i++)
      |                   ~^~~~~~~~~~~~

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