Submission #1275390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275390		k12_khoi	Dreaming (IOI13_dreaming)	C++17	18 / 100	30 ms	11712 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=2e9+1;

int N,M,L,x,y,z,tplt,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)
{
    res=min(res,max(down[u],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=oo;
        dfsOne(i,-1,0);

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

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

    return res;
}

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