Submission #962098

#	Time	Username	Problem	Language	Result	Execution time	Memory
962098		serkanrashid	Dreaming (IOI13_dreaming)	C++11	0 / 100	43 ms	11384 KiB

dreaming

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

using namespace std;

const int MAXN = 1e5+5;

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

int n;

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

int mind;
vector<int> comp;

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

void dfs_dp(int beg, int gor)
{
    used[beg] = 1;
    int maxch = max(sub[beg],gor);
    mind = min(mind,maxch);
    int 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])
        {
            int 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 comp[0]+comp[1]+L;
}

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