Submission #786005

#	Time	Username	Problem	Language	Result	Execution time	Memory
786005		Sputnik1234	Dreaming (IOI13_dreaming)	C++14	100 / 100	66 ms	15616 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
 
using namespace std;
 
vector<pii>g[100005], cts;
int dis[100005], mx, mxx, p[100005], c;
bool used[100005];
 
void dfs(int v, int par)
{
    used[v]=1;
    for(pii u : g[v])
        if(u.F!=par)
        {
            p[u.F]=v;
            dis[u.F]=dis[v]+u.S;
            if(dis[u.F]>dis[mx]) mx=u.F;
            dfs(u.F, v);
        }
}
 
void path(int v)
{
    //cout<<v<<' '<<max(dis[mx]-dis[v], dis[v])<<' '<<c<<' '<<max(dis[mx]-dis[c], dis[c])<<endl;
    if(max(dis[mx]-dis[v], dis[v])<max(dis[mx]-dis[c], dis[c]))
        c=v;
    if(p[v]==v) return;
    path(p[v]);
}
 
int travelTime(int n, int m, int L, int A[], int B[], int T[])
{
    for(int i=0; i<m; i++)
    {
        g[A[i]+1].pb({B[i]+1, T[i]});
        g[B[i]+1].pb({A[i]+1, T[i]});
    }
    //cout<<endl;
    for(int i=1; i<=n; i++)
        if(!used[i])
        {
            //cout<<i<<endl;
            mx=i; dis[i]=0;
            dfs(i, 0); mxx=mx;
            //cout<<mx<<endl;
            dis[mxx]=0; p[mxx]=mxx; mx=i;
            dfs(mxx, 0);
            //cout<<mx<<endl;
            c=mx;
            path(mx);
            //cout<<c<<endl<<endl;
            cts.pb({max(dis[mx]-dis[c], dis[c]), c});
        }
    sort(cts.begin(), cts.end());
    //cout<<endl<<cts[cts.size()-1].F<<' '<<cts[cts.size()-1].S<<endl;
    for(int i=0; i<(int)cts.size()-1; i++)
    {
        g[cts[i].S].pb({cts[cts.size()-1].S, L});
        g[cts[cts.size()-1].S].pb({cts[i].S, L});
    }
    /*
    cout<<endl;
    for(int i=1; i<=n; i++)
    {
        cout<<i<<" ->\n";
        for(pii u : g[i]) cout<<u.F<<' '<<u.S<<endl;
        cout<<endl;
    }
    */
    mx=1, dis[1]=0;
    dfs(1, 0); mxx=mx;
    dis[mxx]=0; mx=0;
    dfs(mxx, 0);
    return dis[mx];
}
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/

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