oj.uz

Submission #557176

# Submission time Handle Problem Language Result Execution time Memory
557176 2022-05-04T20:22:07 Z ljuba Dreaming (IOI13_dreaming) C++17
0 / 100
 109 ms 21068 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
#include <vector>
    
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 -= d[l];
    l = up[l][0];
    if(l != -1) {
        odg -= 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) {
                najjace = min(najjace, max(nadji(a, z), nadji(b, z)));
            }
            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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 21068 KB Output is correct
2 Correct 109 ms 20948 KB Output is correct
3 Correct 79 ms 14660 KB Output is correct
4 Correct 13 ms 5308 KB Output is correct
5 Correct 10 ms 4312 KB Output is correct
6 Correct 20 ms 6776 KB Output is correct
7 Incorrect 3 ms 2744 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 21068 KB Output is correct
2 Correct 109 ms 20948 KB Output is correct
3 Correct 79 ms 14660 KB Output is correct
4 Correct 13 ms 5308 KB Output is correct
5 Correct 10 ms 4312 KB Output is correct
6 Correct 20 ms 6776 KB Output is correct
7 Incorrect 3 ms 2744 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 13908 KB Output is correct
2 Incorrect 58 ms 13900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 21068 KB Output is correct
2 Correct 109 ms 20948 KB Output is correct
3 Correct 79 ms 14660 KB Output is correct
4 Correct 13 ms 5308 KB Output is correct
5 Correct 10 ms 4312 KB Output is correct
6 Correct 20 ms 6776 KB Output is correct
7 Incorrect 3 ms 2744 KB Output isn't correct
8 Halted 0 ms 0 KB -