Submission #492114

#	Time	Username	Problem	Language	Result	Execution time	Memory
492114		aci	Dreaming (IOI13_dreaming)	C++14	0 / 100	74 ms	14000 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define INF 1000000
typedef pair<int, int> pi;

vector<vector<pi>> t;
vector<bool> used;
vector<bool> used2;


int n, m, l;
int d, r;
vector<pi> dist;
vector<int> el;

void dfs1(int u, int p)
{
    used[u] = 1;
    el.push_back(u);
    for (pi v : t[u])
    {
        if(v.first!=p && !used[v.first])
        {
            dist[v.first].first = dist[u].first + v.second;
            dfs1(v.first, u);
        }
    }
}

void dfs2(int u, int p)
{
    used2[u] = 1;
    for (pi v : t[u])
    {
        if(v.first!=p && !used2[v.first])
        {
            dist[v.first].second = dist[u].second + v.second;
            dfs2(v.first, u);
        }
    }
}
void dfs3(int u, int p)
{
    used2[u] = 1;
    for (pi v : t[u])
    {
        if(v.first!=p && !used2[v.first])
        {
            dist[v.first].first = dist[u].first + v.second;
            dfs3(v.first, u);
        }
    }
}

bool cmp(pi a, pi b)
{
    return (a.second > b.second);
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
    
    n = N;
    m = M;
    l = L;

    t.resize(n);
    used.resize(n, 0);
    dist.resize(n, {-1, -1});
    used2.resize(n, 0);

    for (int i=0; i<m; i++)
    {
        int x, y, w;
        x = A[i];
        y = B[i];
        w = T[i];

        t[x].push_back({y, w});
        t[y].push_back({x, w});
    }
    vector<pi> comp;
    

    for (int i=0; i<n; i++)
    {
        
        if(!used[i])
        {
            
            dist[i].first =0;
            el.clear();
            dfs1(i, i);
            //cout<< endl;
            used2.assign(n, 0);
            int ind=i, mx = 0;
            d = 0;
            r = INF;
            for (int j : el)
            {
                if(dist[j].first > mx)
                {
                    mx = dist[j].first;
                    ind = j;
                }
            }

            dist[ind].second = 0;
            dfs2(ind, ind);
            
    
            for (int j : el)
            {
                if(dist[j].second > d)
                {
                    d = dist[j].second;
                    ind = j;
                }
            }
            used2.assign(n, 0);
            dist[ind].first = 0;
            dfs3(ind, ind);
            //for (int j : el) //cout<<j<<" "<< dist[j].first<<" "<<dist[j].second<<endl;
            for (int j : el)
            {
                if(dist[j].first==-1) dist[j].first = INF;
                if(dist[j].second==-1) dist[j].second = INF;
                r = min(r, max(dist[j].first, dist[j].second));
            }
            comp.push_back({d, r});

        }
    }
    sort(comp.begin(), comp.end(), cmp);
    int res = 0;
    for (auto x : comp) res = max(res, x.first);
    res = max(res, max(comp[0].second+l+comp[1].second, 2*l+comp[1].second+comp[2].second));

    //for (auto x : comp) //cout<< x.first<<" "<<x.second<<endl;


    return res;

}

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