Submission #1012426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012426		parsadox2	Dreaming (IOI13_dreaming)	C++17	100 / 100	55 ms	17832 KiB

dreaming

#include <bits/stdc++.h>
#include <dreaming.h>
#define F first
#define S second
using namespace std;

const int N = 1e5 + 10;
vector <pair <int , int>> adj[N];
vector <int> mn , all;
bool marked[N];
int dis[N] , dis2[N];

void Dfs(int v , int p = -1)
{
    //cout << v << endl;
    marked[v] = true;
    all.push_back(v);
    for(auto u : adj[v])  if(u.F != p)
    {
        dis[u.F] = dis[v] + u.S;
        Dfs(u.F , v);
    }
}

void Dfs2(int v , int p = -1)
{
    //cout << "!" << v << endl;
    for(auto u : adj[v])  if(u.F != p)
    {
        dis2[u.F] = dis2[v] + u.S;
        dis[u.F] = max(dis[u.F] , dis2[u.F]);
        Dfs2(u.F , v);
    }
}

int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
    for(int i = 0 ; i < m ; i++)
    {
        adj[A[i]].push_back(make_pair(B[i] , T[i]));
        adj[B[i]].push_back(make_pair(A[i] , T[i]));
    }
    int ans = 0;
    for(int i = 0 ; i < n ; i++)  if(!marked[i])
    {
        all.clear();
        Dfs(i);
        int v = i;
        for(auto u : all)  if(dis[u] > dis[v])
            v = u;
        dis[v] = 0;
        all.clear();
        Dfs(v);
        int v2 = i;
        for(auto u : all)  if(u != v && dis[u] > dis[v2])
            v2 = u;
        ans = max(ans , dis[v2]);
        Dfs2(v2);
        int x = dis[i];
        for(auto u : all)
            x = min(dis[u] , x);
        mn.push_back(x);
    }
    sort(mn.rbegin() , mn.rend());
    if(n - m >= 2)
        ans = max(ans , mn[0] + mn[1] + l);
    if(n - m >= 3)
        ans = max(ans , mn[1] + mn[2] + 2 * l);
    return ans;
}

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