oj.uz

Submission #557188

# Submission time Handle Problem Language Result Execution time Memory
557188 2022-05-04T20:42:31 Z ljuba Dreaming (IOI13_dreaming) C++17
0 / 100
 1000 ms 21000 KB 
#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);
            int najjace = INT_MAX;
            for(auto z : posetili) {
                int gas = 0;
                for(auto x : posetili) {
                    gas = max(gas, nadji(z, x)); //zasto ne radis?!?!?
                    ans = max(ans, nadji(z, x));
                }
                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;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:129:17: warning: unused variable 'b' [-Wunused-variable]
  129 |             int b = nadjiNajdalji(a);
      |                 ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 21000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 21000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 13880 KB Output is correct
2 Incorrect 35 ms 13936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 21000 KB Time limit exceeded
2 Halted 0 ms 0 KB -