oj.uz

Submission #797796

# Submission time Handle Problem Language Result Execution time Memory
797796 2023-07-29T23:20:47 Z gg123_pe Dreaming (IOI13_dreaming) C++14
0 / 100
 33 ms 16444 KB 
#include "dreaming.h"
#include <bits/stdc++.h> 
using namespace std; 

#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 1e5 + 5; 

int n; 
int d[N], p[N], W[N]; 
vector <pair<int,int>> adj[N]; 
vector <int> used; 

void dfs(int u, int f){
    used.push_back(u);  
    for(auto pa: adj[u]){
        int v = pa.first, w = pa.second; 
        if(v == f) continue;
        d[v] = d[u] + w; 
        p[v] = u, W[v] = w; 
        dfs(v, u); 
    }
}
pair<int,int> get(int u){
    d[u] = 0, p[u] = -1, W[u] = 0; 
    used.clear(); 
    dfs(u, -1); 
    int node = -1, maxi = -1; 
    for(int u: used){
        if(d[u] > maxi){
            maxi = d[u], node = u; 
        }
    }
    return {node, maxi}; 
}
int travelTime(int Ni, int M, int L, int A[], int B[], int T[]) {
    n = Ni; 

    f(i,0,M){
        adj[A[i]].push_back({B[i], T[i]});  
        adj[B[i]].push_back({A[i], T[i]}); 
    }

    memset(d, -1, sizeof d); 

    int x = -1, y = -1, z = -1; 
    f(i,0,n){
        if(d[i] != -1) continue; 
        auto ra = get(i); 
        auto ta = get(ra.first);
        int leaf = ta.first, dim = ta.second; 
        int curr = 0, mini = dim; 

        while(leaf != ra.first){
            curr += W[leaf]; 
            mini = min(mini, max(curr, abs(dim - curr))); 
            leaf = p[leaf]; 
        }
        if(mini > x) z = y, y = x, x = mini; 
        else if(mini > y) z = y, y = mini; 
        else if(mini > z) z = mini; 
    }
    int ans = x + y + L; 
    if(z != -1) ans = max(ans, y + z + 2*L); 

    return ans;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6516 KB Output is correct
2 Correct 15 ms 6484 KB Output is correct
3 Correct 14 ms 6484 KB Output is correct
4 Correct 13 ms 6480 KB Output is correct
5 Correct 13 ms 6484 KB Output is correct
6 Correct 14 ms 6644 KB Output is correct
7 Correct 14 ms 6652 KB Output is correct
8 Correct 13 ms 6356 KB Output is correct
9 Correct 12 ms 6420 KB Output is correct
10 Correct 13 ms 6612 KB Output is correct
11 Correct 2 ms 3052 KB Output is correct
12 Correct 3 ms 3796 KB Output is correct
13 Correct 4 ms 3828 KB Output is correct
14 Correct 3 ms 3796 KB Output is correct
15 Correct 3 ms 3796 KB Output is correct
16 Correct 3 ms 3816 KB Output is correct
17 Correct 4 ms 3812 KB Output is correct
18 Correct 4 ms 3796 KB Output is correct
19 Correct 3 ms 3796 KB Output is correct
20 Incorrect 1 ms 3028 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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