Submission #433067

#	Time	Username	Problem	Language	Result	Execution time	Memory
433067		MilosMilutinovic	Dreaming (IOI13_dreaming)	C++14	100 / 100	112 ms	17264 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define MAXN 100007
using namespace std;
int dist[MAXN],par[MAXN];
vector<pair<int,int>> g[MAXN];
bool vis[MAXN];
void dfs1(int u,int p,int& i)
{
    if(dist[u]>dist[i])i=u;
    if(p==-1)dist[u]=0;
    par[u]=p;
    for(auto [v,w]:g[u])
    {
        if(v==p)continue;
        dist[v]=dist[u]+w;
        dfs1(v,u,i);
    }
}
void dfs2(int u,int p)
{
    vis[u]=true;
    for(auto [v,w]:g[u])if(v!=p)dfs2(v,u);
}
int travelTime(int n, int m, int l, int* a, int* b, int* t)
{
    for(int i=0;i<n;i++)g[i].clear();
    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]});
    }
    int mx=0;
    vector<int> c;
    for(int i=0;i<n;i++)
    {
        if(vis[i])continue;
        int ind1=i;dfs1(i,-1,ind1);
        int ind2=i;dfs1(ind1,-1,ind2);
        int d=dist[ind2];mx=max(mx,d);
        for(int j=ind2;j>=0;j=par[j])d=min(d,max(dist[j],dist[ind2]-dist[j]));
        c.push_back(d);
        dfs2(i,-1);
    }
    sort(c.rbegin(),c.rend());
    assert(!c.empty());
    if(c.size()==1)return max(mx,c[0]);
    if(c.size()==2)return max(mx,c[0]+c[1]+l);
    return max({mx,c[0]+c[1]+l,c[1]+c[2]+2*l});
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int, int, int&)':
dreaming.cpp:13:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   13 |     for(auto [v,w]:g[u])
      |              ^
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for(auto [v,w]:g[u])if(v!=p)dfs2(v,u);
      |              ^

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