Submission #110953

#	Time	Username	Problem	Language	Result	Execution time	Memory
110953		The_Wolfpack	Dreaming (IOI13_dreaming)	C++14	100 / 100	100 ms	15864 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;

const int NMAX=1e5+7;

int vis[NMAX];
pii mx1[NMAX],mx2[NMAX];
vector<pii> g[NMAX];

int ans=0;
int naj=1e9+7;
void dfs(int son, int par)
{
    vis[son]=1;
    for(pii nxt:g[son])
    {
        if(nxt.x==par) continue;
        dfs(nxt.x,son);
        pii tmp={mx1[nxt.x].x+nxt.y,nxt.x};
        if(tmp>mx1[son]) swap(mx1[son],tmp);
        if(tmp>mx2[son]) swap(mx2[son],tmp);
    }
    ans=max(ans,mx1[son].x+mx2[son].x);
}

void nadji(int son, int par, int d)
{
    naj=min(naj,max(d,mx1[son].x));
    for(pii nxt:g[son])
    {
        if(nxt.x==par) continue;
        int dub2=nxt.y+max(d,(nxt.x==mx1[son].y)?mx2[son].x:mx1[son].x);
        nadji(nxt.x,son,dub2);
    }
}

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]});
    }
    vector<int> rad;
    for(int i=0;i<N;i++)
    {
        if(!vis[i])
        {
            dfs(i,-1);
            naj=1e9+7;
            nadji(i,-1,0);
            rad.push_back(naj);
        }
    }
    sort(rad.rbegin(),rad.rend());
    if(rad.size()>=2) ans=max(ans,rad[0]+rad[1]+L);
    if(rad.size()>=3) ans=max(ans,rad[1]+rad[2]+2*L);
    return ans;
}

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