Submission #469982

#	Time	Username	Problem	Language	Result	Execution time	Memory
469982		Newtech66	Dreaming (IOI13_dreaming)	C++17	18 / 100	1094 ms	12780 KiB

dreaming

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

int dfs(int u,const vector<vector<pair<int,int> > >& g,int p=-1)
{
    int mx=0;
    for(auto [v,w]:g[u])
    {
        if(v==p)  continue;
        mx=max(mx,w+dfs(v,g,u));
    }
    return mx;
}

int getrep(int u,const vector<vector<pair<int,int> > >& g,vector<bool>& vis,const vector<int>& D)
{
    vis[u]=true;
    int mn=D[u];
    for(auto [v,w]:g[u])
    {
        if(vis[v])   continue;
        mn=min(mn,getrep(v,g,vis,D));
    }
    return mn;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vector<vector<pair<int,int> > > g(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]});
    }
    vector<int> D(N);
    vector<int> reps;
    for(int i=0;i<N;i++)
    {
        D[i]=dfs(i,g);
    }
    vector<bool> vis(N,false);
    for(int i=0;i<N;i++)
    {
        if(vis[i])  continue;
        reps.push_back(getrep(i,g,vis,D));
    }
    sort(reps.rbegin(),reps.rend());
    int ans=reps[0];
    if(reps.size()>1)    ans=max(ans,L+reps[0]+reps[1]);
    if(reps.size()>2)    ans=max(ans,2*L+reps[1]+reps[2]);
    return ans;
}

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