Submission #1275404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275404		k12_khoi	Dreaming (IOI13_dreaming)	C++17	100 / 100	45 ms	16064 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int MAXN=1e5+5;
const int oo=INT_MAX;

int N,M,L,x,y,z,tplt,mi,res;
int A[MAXN],B[MAXN],T[MAXN],down[MAXN],best[MAXN][2],ma[3];
bool visited[MAXN];
vector <pii> adj[MAXN];

void pre_dfs(int u,int par)
{
    visited[u]=true;
    down[u]=0;
    best[u][0]=best[u][1]=0;
    for (pii v:adj[u])
    if (v.Y!=par)
    {
        pre_dfs(v.Y,u);
        down[u]=max(down[u],down[v.Y]+v.X);
        if (best[u][0]<down[v.Y]+v.X)
        {
            best[u][1]=best[u][0];
            best[u][0]=down[v.Y]+v.X;
        }
        else if (best[u][1]<down[v.Y]+v.X) best[u][1]=down[v.Y]+v.X;
    }
}

void dfsOne(int u,int par,int ma)
{
    mi=min(mi,max(down[u],ma));
    res=max(res,ma);

    for (pii v:adj[u])
    if (v.Y!=par)
    {
        if (best[u][0]==down[v.Y]+v.X) dfsOne(v.Y,u,max(best[u][1],ma)+v.X);
        else dfsOne(v.Y,u,max(best[u][0],ma+v.X));
    }
}

int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
    for (int i=0;i<M;i++)
    {
        x=A[i];
        y=B[i];
        z=T[i];

        adj[x].push_back(make_pair(z,y));
        adj[y].push_back(make_pair(z,x));
    }

    tplt=0;
    for (int i=0;i<N;i++)
    if (!visited[i])
    {
        tplt++;

        pre_dfs(i,-1);

        res=max(res,down[i]);

        mi=oo;
        dfsOne(i,-1,0);

        if (ma[0]<mi)
        {
            ma[2]=ma[1];
            ma[1]=ma[0];
            ma[0]=mi;
        }
        else if (ma[1]<mi)
        {
            ma[2]=ma[1];
            ma[1]=mi;
        }
        else if (ma[2]<mi) ma[2]=mi;
    }

    if (tplt==1) res=max(res,down[0]);
    else if (tplt==2) res=max(res,ma[0]+ma[1]+L);
    else res=max(res,max(ma[2]+L,ma[0])+ma[1]+L);

    return res;
}

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