Submission #1039939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039939		pawned	Dreaming (IOI13_dreaming)	C++17	100 / 100	48 ms	16880 KiB

dreaming

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "dreaming.h"

const int MAX = 1e5 + 5;

int N, M, L;

vector<ii> adj[MAX];    // {vertex, dist}

bool vis[MAX];

int timer = 0;

vector<vi> inc;     // in component x
vi comp(MAX, -1);   // component number

void dfs(int n) {
    vis[n] = true;
    inc.back().pb(n);
    comp[n] = timer;
    for (ii x : adj[n]) {
        if (!vis[x.fi]) {
            vis[x.fi] = true;
            dfs(x.fi);
        }
    }
}

vi dist(MAX, 1e9);  // prelim dist
vi dist2(MAX, 1e9); // distance from v1

int fardia = 0;

ii findDia(int n) {   // find diameter of component v
    queue<int> q;
    q.push(inc[n][0]);
    dist[inc[n][0]] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (ii y : adj[x]) {
            if (dist[y.fi] == 1e9) {
                dist[y.fi] = dist[x] + y.se;
                q.push(y.fi);
            }
        }
    }
    // find farthest among connected
    int maxd = -1;
    int v1 = -1;
    for (int x : inc[n]) {
        if (dist[x] > maxd) {
            maxd = dist[x];
            v1 = x;
        }
    }
    // bfs from v1
    // q is already empty
    q.push(v1);
    dist2[v1] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (ii y : adj[x]) {
            if (dist2[y.fi] == 1e9) {
                dist2[y.fi] = dist2[x] + y.se;
                q.push(y.fi);
            }
        }
    }
    maxd = -1;
    int v2 = -1;
    for (int x : inc[n]) {
        if (dist2[x] > maxd) {
            maxd = dist2[x];
            v2 = x;
        }
    }
    fardia = max(fardia, maxd);
//    cout<<"have "<<v1<<" "<<v2<<" "<<maxd<<endl;
    return {v1, v2};
}

vi dist3(MAX, 1e9); // distance from v2

int mindist(int n, ii dia) {
    queue<int> q;
    q.push(dia.se);
    dist3[dia.se] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (ii y : adj[x]) {
            if (dist3[y.fi] == 1e9) {
                dist3[y.fi] = dist3[x] + y.se;
                q.push(y.fi);
            }
        }
    }
    int minv = 1e9;
    for (int x : inc[n]) {
        minv = min(minv, max(dist2[x], dist3[x]));
    }
    return minv;
}

int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
    N = n; M = m; L = l;
    for (int i = 0; i < M; i++) {
        adj[A[i]].pb({B[i], T[i]});
        adj[B[i]].pb({A[i], T[i]});
    }
    for (int i = 0; i < N; i++) {
        if (!vis[i]) {
            inc.pb({});
            dfs(i);
            timer++;
        }
    }
    int K = inc.size();
/*    cout<<"inc: "<<endl;
    for (int i = 0; i < K; i++) {
        cout<<i<<": ";
        for (int x : inc[i])
            cout<<x<<" ";
        cout<<endl;
    }*/
    vi allv;
    for (int i = 0; i < K; i++) {
        ii dia = findDia(i);
//        cout<<i<<": "<<dia.fi<<", "<<dia.se<<endl;
        int distr = mindist(i, dia);
//        cout<<"distr: "<<distr<<endl;
        allv.pb(distr);
    }
    sort(allv.begin(), allv.end(), greater<int>());
/*    cout<<"allv: ";
    for (int x : allv)
        cout<<x<<" ";
    cout<<endl;*/
    if (M == N - 1) {
        return fardia;
    }
    int ans = fardia;
    ans = max(ans, L + allv[0] + allv[1]);
    if (M < N - 2)
        ans = max(ans, 2 * L + allv[1] + allv[2]);
    // for each component, find point that has min farthest dist
    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