Submission #557190

#	Time	Username	Problem	Language	Result	Execution time	Memory
557190		ljuba	Dreaming (IOI13_dreaming)	C++17	14 / 100	106 ms	21188 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
    
using namespace std;
    
int n;
    
const int mxN = 1e5 + 12;
bool vis[mxN];

int d[mxN];
    
vector<pair<int, int>> adj[mxN];

const int LG = 20;
int up[mxN][LG];
int dep[mxN];
 
void dfs(int s, int p = -1) {
    vis[s] = true;
    if(p == -1) {
        d[s] = 0;
        dep[s] = 0;
    } else {
        dep[s] = dep[p] + 1;
    }

    up[s][0] = p;
    for(int i = 1; i < LG; ++i) {
        if(up[s][i-1] == -1) {
            up[s][i] = -1;
        } else {
            up[s][i] = up[up[s][i-1]][i-1];
        }
    }

    for(auto iv : adj[s]) {
        int e = iv.first;
        int w = iv.second;
    
        if(e == p) continue;
        d[e] = d[s] + w;
        dfs(e, s);
    }
}
    
int dist[mxN];
    
vector<int> posetili;
    
void dfsNajdalji(int s, int p = -1) {
    if(p == -1) {
        dist[s] = 0;
    }
    
    posetili.push_back(s);
    
    for(auto iv : adj[s]) {
        int e = iv.first;
        int w = iv.second;
    
        if(e == p) continue;
        dist[e] = dist[s] + w;
        dfsNajdalji(e, s);
    }
}

int nadjiNajdalji(int s) {
    posetili.clear();
    dfsNajdalji(s);
    
    pair<int, int> p{-1, -1};
    for(auto i : posetili) {
        pair<int, int> temp{dist[i], i};
        p = max(p, temp);
    }
    
    return p.second;
}

int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);

    int k = dep[u] - dep[v];

    for(int i = LG-1; i >= 0; --i) {
        if((k>>i)&1) {
            u = up[u][i];
        }
    }

    if(u == v) return u;

    for(int i = LG-1; i >= 0; --i) {
        if(up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[u][i];
        }
    }

    return up[u][0];
}

inline int nadji(int u, int v) {
    int l = lca(u, v);
    int odg = d[u] + d[v];
    odg -= 2*d[l];
    return odg;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n = N;
    for(int i = 0; i < M; ++i) {
        int u = A[i];
        int v = B[i];
        int w = T[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<int> svi;
    
    int ans = 0;
    
    for(int i = 0; i < n; ++i) {
        if(!vis[i]) {
            dfs(i);
            int a = nadjiNajdalji(i);
            int b = nadjiNajdalji(a);
            ans = max(ans, nadji(a, b));
            int najjace = INT_MAX;
            for(auto z : posetili) {
                int gas = max(nadji(z, a), nadji(z, b));
                najjace = min(najjace, gas);
            }
            svi.push_back(najjace);
        }
    }
    
    sort(svi.rbegin(), svi.rend());
    
    if(svi.size() > 1) {
        ans = max(ans, svi[0] + svi[1] + L);
    }
    
    return ans;
}

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