Submission #962162

#	Time	Username	Problem	Language	Result	Execution time	Memory
962162		serkanrashid	Dreaming (IOI13_dreaming)	C++14	47 / 100	74 ms	18288 KiB

dreaming

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

using namespace std;

const int MAXN = 1e5+5;

struct edge
{
    long long ver,dist;
    edge(){};
    edge(int vi, long long di)
    {
        ver = vi;
        dist = di;
    }
};

int n;

vector<edge> g[MAXN];
long long sub[MAXN],used[MAXN];

long long mind,vut;
vector<long long> comp;

void clear_used()
{
    for(int i = 0; i < n; i++) used[i] = 0;
}

void dfs_dp(int beg, long long gor)
{
    used[beg] = 1;
    long long maxch = max(sub[beg],gor);
    vut = max(vut,maxch);
    mind = min(mind,maxch);
    long long fir = 0, sec = 0;
    for(edge nb : g[beg])
    {
        if(!used[nb.ver])
        {
            if(nb.dist+sub[nb.ver] >= fir)
            {
                sec = fir;
                fir = nb.dist+sub[nb.ver];
            }
            else if(nb.dist+sub[nb.ver] >= sec)
            {
                sec = nb.dist+sub[nb.ver];
            }
        }
    }
    for(edge nb : g[beg])
    {
        if(!used[nb.ver])
        {
            long long new_gor = gor;
            if(nb.dist+sub[nb.ver] == fir) new_gor = max(new_gor,sec);
            else new_gor = max(new_gor,fir);
            new_gor += nb.dist;
            dfs_dp(nb.ver,new_gor);
        }
    }
}

void dfs(int beg)
{
    used[beg] = 1;
    for(edge nb : g[beg])
    {
        if(!used[nb.ver])
        {
            dfs(nb.ver);
            sub[beg] = max(sub[beg],sub[nb.ver]+nb.dist);
        }
    }
}

int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
    n = N;
    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]});
    }
    for(int i = 0; i < N; i++) if(!used[i]) dfs(i);
    clear_used();
    for(int i = 0; i < N; i++)
    {
        if(!used[i])
        {
            mind = 1e9+5;
            dfs_dp(i,0);
            comp.push_back(mind);
        }
    }
    return max(comp[0]+comp[1]+L,vut);
}

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