제출 #920107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
920107		Juanchoki	Dreaming (IOI13_dreaming)	C++14	100 / 100	599 ms	33872 KiB

dreaming

#include"dreaming.h"
#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int u, w;
};
struct tpos
{
    int nodo, dist, padre;
};
int maxn;
const int MAXN = 2e5 + 4;
int Visi[MAXN];
vector<vector<edge>> adj;
struct Component 
{
    int first;
    int second;
};
bool operator < (const Component& a, const Component& b) { return a.second < b.second; }
Component bfs (int nodo)
{
        Component ret;
        ret.second = -1;
        queue<tpos> q; 
        q.push({nodo, 0, -1});
        tpos temp_tpos;
        vector<bool> visi(maxn);
        while (!q.empty())
        {
            temp_tpos = q.front(); q.pop();
            visi[temp_tpos.nodo] = 1;
            Visi[temp_tpos.nodo] = 1;
            //cout << "    " << temp_tpos.nodo <<  " " << temp_tpos.dist << "\n";
            for (edge e: adj[temp_tpos.nodo])
            {
           //     cout << temp_tpos.nodo << " vecinos: " << e.u << '\n';
                if (visi[e.u]) continue;
                q.push({e.u, temp_tpos.dist+e.w, temp_tpos.nodo}); 
            }
            if (temp_tpos.dist > ret.second)
            {
                ret.second = temp_tpos.dist;
                ret.first = temp_tpos.nodo;
            }
        }
    //cout << '\n';
    return ret;
}
tpos Diametro (int pos)
{
    int ve = bfs(pos).first;
    tpos ttpos;
    ttpos.nodo = ve;
    Component par = bfs(ve);
    ttpos.dist = par.first;
    ttpos.padre = par.second;
    return ttpos;
}

void DFS(int nodo, int dist, map<int, bool> &visit, map<int, int> &ret)
{
    visit[nodo] = 1;
    ret[nodo] = dist;
    for (edge &e: adj[nodo])
        if (visit[e.u]) continue;
        else DFS(e.u, dist + e.w, visit, ret);
}

int distanciaxdd (int nodo, map<int, bool> &visit, map<int, int> &a, map<int, int> &b)
{
    visit[nodo] = 1;
    int mini = max(a[nodo], b[nodo]);
    for (edge &e: adj[nodo])
        if (visit[e.u]) continue;
        else mini = min (mini, distanciaxdd(e.u, visit, a, b));
    return mini;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
    maxn = N;
    adj.resize(N);
    edge temp_edge;
    for (int i = 0; i < M; i++)
    {
        temp_edge.u = B[i];
        temp_edge.w = T[i];
        adj[A[i]].push_back(temp_edge);
        temp_edge.u = A[i];
        adj[B[i]].push_back(temp_edge);
    }
    priority_queue<Component> pq;
    Component par;

    for (int i = 0; i < N; i++)
    {
        if (Visi[i]) continue;
        tpos ttpos = Diametro(i);
        par.first = ttpos.padre;
        map<int, int> uno, dos;
        map<int, bool> visit;
        DFS(ttpos.nodo, 0, visit, uno);
        visit.clear();
        DFS(ttpos.dist, 0, visit, dos);
        visit.clear();
        par.second = distanciaxdd(i, visit, uno, dos);
       // cout << i << " " << par.first << " " << par.second << '\n';
        pq.push(par);
    }
        
    while (pq.size() > 1)
    {
        Component a1 = pq.top(); pq.pop();
        Component a2 = pq.top(); pq.pop();
     //   cout << a1.first << ' ' << a2.first << '\n';
        Component temporal;
        temporal.first = max(a1.first, max(a2.first, a1.second + a2.second + L));
        temporal.second = min (max (a1.second + L, a2.second), max(a2.second + L, a1.second));
        pq.push(temporal);
    }

    return pq.top().first;
    return 1;
}

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