Submission #67959

#	Time	Username	Problem	Language	Result	Execution time	Memory
67959		andy627	Dreaming (IOI13_dreaming)	C++17	100 / 100	127 ms	15608 KiB

dreaming

#include "dreaming.h"

#include <stdio.h>
#include <vector>
#include <algorithm>
#define pii pair<int,int>
#define ff first
#define ss second
#define INF 2e9
using namespace std;

vector<pii> edge[111111];
bool used[111111],is_gone[111111];

int dist[111111],path[111111];
vector<pii> vc_d;

vector<int> vc_r;

pii dfs_mx(int v){
    pii mx={0,v};

    is_gone[v]=1; used[v]=1;
    for(int i=0;i<edge[v].size();i++){
        if(is_gone[edge[v][i].ff]) continue;
        dist[edge[v][i].ff]=dist[v]+edge[v][i].ss;

        pii res=dfs_mx(edge[v][i].ff);
        if(mx.ff<res.ff+edge[v][i].ss){
            mx.ff=res.ff+edge[v][i].ss;
            mx.ss=res.ss;
        }
    }
    is_gone[v]=0;
    path[v]=mx.ss;

    return mx;
}

void line(int v,int far){
    if(path[v]!=far) return;
    vc_d.push_back({dist[v],v});

    is_gone[v]=1;
    for(int i=0;i<edge[v].size();i++){
        if(is_gone[edge[v][i].ff]) continue;
        line(edge[v][i].ff,far);
    }
    is_gone[v]=0;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i=0;i<M;i++){
        edge[A[i]].push_back({B[i],T[i]});
        edge[B[i]].push_back({A[i],T[i]});
    }

    int ans=0;
    for(int i=0;i<N;i++){
        if(used[i]) continue;

        dist[i]=0;
        int rt=dfs_mx(i).ss;

        dist[rt]=0;
        pii res=dfs_mx(rt);
        int d=res.ff,far=res.ss; ans=max(ans,d);

        line(rt,far);

        int mn=INF;
        for(auto v:vc_d) mn=min(mn,max(v.ff,d-v.ff));
        vc_r.push_back(mn); vc_d.clear();
    }

    sort(vc_r.begin(),vc_r.end());

    int siz=vc_r.size();
    if(siz>=2) ans=max(ans,vc_r[siz-1]+vc_r[siz-2]+L);
    if(siz>=3) ans=max(ans,vc_r[siz-2]+vc_r[siz-3]+(L<<1));

    return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'std::pair<int, int> dfs_mx(int)':
dreaming.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<edge[v].size();i++){
                 ~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void line(int, int)':
dreaming.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<edge[v].size();i++){
                 ~^~~~~~~~~~~~~~~

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