Submission #1179085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179085		pensive	Dreaming (IOI13_dreaming)	C++20	100 / 100	63 ms	11336 KiB

dreaming

#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#include <tuple>
#include "dreaming.h"

using namespace std;
#define ll long long
#define REP(a,i,n) for (int i=a;i<n;i++)
#define f first
#define s second

pair<int, ll> bfs(vector<ll> &distances, int root, vector< vector<pair<int, ll> > > &adj) {
    queue<int> q;
    q.push(root); distances[root] = 0;
    ll mx = 0, mxNode=root;
    while (q.empty()==false) {
        int node = q.front();
        q.pop();
        if (distances[node] > mx) {
            mx = distances[node];
            mxNode = node;
        }
        for (auto [m, x] : adj[node]) {
            if (distances[m]!=-1) continue;
            distances[m] = distances[node] + x;
            q.push(m);
        }
    }
    return make_pair(mxNode, mx);
}

ll lastBFS(vector<ll> &distances, vector<ll> &otherEnd, int root, vector< vector<pair<int, ll> > > &adj) {
    queue<int> q;
    q.push(root); distances[root] = 0;
    ll radius=1e10;
    while (q.empty()==false) {
        int node = q.front();
        q.pop();
        ll maxDist = max(distances[node], otherEnd[node]);
        radius = min(radius, maxDist);
        for (auto [m, x] : adj[node]) {
            if (distances[m]!=-1) continue;
            distances[m] = distances[node] + x;
            q.push(m);
        }
    }
    return radius;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vector< vector<pair<int, ll> > > adj(N+1);
    REP(0,i,M) {
        adj[A[i]].emplace_back(B[i], T[i]);
        adj[B[i]].emplace_back(A[i], T[i]);
    }
    vector<pair<int, int>> ends;
    vector<ll> dia;
    vector<ll> arbiRoot(N+1, -1), distances(N+1, -1);
    int end1; ll dist;
    REP(0, i, N) {
        if (arbiRoot[i]==-1) {
            tie(end1, dist) = bfs(arbiRoot, i, adj);
            ends.emplace_back(end1, 0);
            //cout << "Arbitrary root at " << i << "-> " << dist << " from " << end1 << endl;
        }
    }
    arbiRoot.clear(); arbiRoot.resize(N+1, -1);
    REP(0, i, ends.size()) {
        if (arbiRoot[ends[i].f]==-1) {
            tie(end1, dist) = bfs(arbiRoot, ends[i].f, adj);
            ends[i].s = end1;
            dia.push_back(dist); //diameter
        }
    }
    vector<ll> radii;
    REP(0,i,ends.size()) {
        if (distances[ends[i].s]==-1) {
            radii.push_back(lastBFS(distances, arbiRoot, ends[i].s, adj));
            //cout << "ROOT " << ends[i].s << ": " <<dia[i] << " " << radii[i] << endl;
        }
    }
    ll maxDiameter=0;
    for (ll diam : dia) {
        maxDiameter = max(maxDiameter, diam);
    }
    if (radii.size()==1)
        return maxDiameter;
    sort(radii.begin(), radii.end(), greater<>());
    ll first = radii[0] + radii[1] + L;
    if (radii.size()==2) return max(maxDiameter, first);
    ll second = radii[1] + radii[2] + 2*L;
    return max(first, max(second, maxDiameter));
}

/*
int main() {
    int A[] = {0, 8, 2, 5, 5, 1, 1, 10}, B[] = {8, 2, 7, 11, 1, 3, 9, 6};
    int T[] = {4, 2, 4, 3, 7, 1, 5, 3};
    cout << travelTime(12,8,2,A,B,T);
    return 0;
}*/

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