Submission #253390

#	Time	Username	Problem	Language	Result	Execution time	Memory
253390		ChrisT	Dreaming (IOI13_dreaming)	C++17	100 / 100	114 ms	10620 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define pii pair<int,int>
#define piii pair<int,pii>
#define MAXN 100000
#define ll long long int
#define pil pair<int,ll>
vector<pii> adj[MAXN];
bool vis[MAXN];
int dist[MAXN], dist2[MAXN];
int last[MAXN];
queue<int> q;
pii furthest (int n){
    pii ans = {0,0};
    dist[n] = 0;
    last[n] = -1;
    q.push(n);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (pii p : adj[cur]) if (dist[p.first] == -1) {
            dist[p.first] = dist[cur] + p.second;
            last[p.first] = cur;
            if (dist[p.first] > ans.second) {
                ans.second = dist[p.first];
                ans.first = p.first;
            }
            q.push(p.first);
        }
    }
    return ans;
}
int far (int n) {
    q.push(n);
    int cur = 0, best=0,ans=0;
    dist2[n] = 0;
    while (!q.empty()) {
        cur = q.front();
        if (dist2[cur] > best) {
            best = dist2[cur];
            ans = cur;
        }
        vis[cur] = true;
        q.pop();
        for (pii p : adj[cur]) if (!vis[p.first]) {
                q.push(p.first);
                dist2[p.first] = dist2[cur] + p.second;
        }
    }
    return ans;
}
int travelTime (int N, int M, int L, int A[], int B[], int T[]) {
    memset(dist,-1,sizeof(dist));
    memset(vis,0,sizeof(vis));
    for (int x = 0; x < M; x++) {
        adj[A[x]].push_back({B[x],T[x]});
        adj[B[x]].push_back({A[x],T[x]});
    }
    int components = 0;
    int max1 = 0, max2 = 0, max3 = 0,maxdiam = 0;
    for (int x = 0; x < N; x++) if (!vis[x]) {
        components++;
        if(!adj[x].size()) continue;
        pii diameter = furthest(far(x));
        int cur = diameter.first;
        int dista = diameter.second, radiusish = dista/2, radius = 0;
        maxdiam = max(maxdiam,dista);
        while (dist[last[cur]] > radiusish) cur = last[cur];
        radius = min(max(dist[cur],dista-dist[cur]),max(dist[last[cur]],dista-dist[last[cur]]));
        if (radius >= max1) {
            max3 = max2;
            max2 = max1;
            max1 = radius;
        }
        else if (radius >= max2) {
            max3 = max2;
            max2 = radius;
        }
        else if (radius > max3) max3 = radius;
    }
    if (components == 1) return maxdiam;
    if (components == 2) return max(max1+max2+L,maxdiam);
    return max(max1+max2+L,max(maxdiam,max2+max3+L*2));
}

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