oj.uz

Submission #430683

# Submission time Handle Problem Language Result Execution time Memory
430683 2021-06-16T18:24:42 Z muhammad_hokimiyon Dreaming (IOI13_dreaming) C++14
0 / 100
 1000 ms 12100 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

#define fi first
#define se second
#define ll long long
#define dl double

using namespace std;

const int maxN = 1e5 + 7;

int val,v1,ve;
int d[maxN];
int u[maxN];
bool used[maxN];
vector<pair<int, int>> v[maxN];

void dfs1(int x, int p)
{
        used[x] = true;
        for(auto y : v[x]){
                if(y.fi == p)continue;
                dfs1(y.fi, x);
                d[x] = max(d[x], d[y.fi] + y.se);
        }
}

void dfs2(int x, int p)
{
        int mx1 = -1, mx2 = -1;
        int v1 = -1, v2 = -1;
        for(auto y : v[x]){
                if(y.fi == p)continue;
                if(d[y.fi] > mx1){
                        if(mx1 > mx2){
                                mx2 = mx1;
                                v2 = v1;
                        }
                        mx1 = d[y.fi];
                        v1 = y.fi;
                }else if(d[y.fi] > mx2){
                        mx2 = d[y.fi];
                        v2 = y.fi;
                }
        }
        if(max(u[x], d[x]) > val){
                v1 = x;
        }
        val = min(val, max(u[x], d[x]));
        for(auto y : v[x]){
                if(y.fi == p)continue;
                u[y.fi] = max(u[y.fi], u[x]);
                if(y.fi == v1)u[y.fi] = max(u[y.fi], mx1 + y.se);
                else u[y.fi] = max(u[y.fi], mx2 + y.se);
                dfs2(y.fi, x);
        }
}

void dfs(int x, int p, int sum)
{
        used[x] = true;
        if(sum >= val){
                val = sum;
                ve = x;
        }
        for(auto y : v[x]){
                if(y.first != p){
                        dfs(y.first, x, sum + y.second);
                }
        }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
        for(int i = 0; i < M; i++){
                v[A[i]].push_back({B[i], T[i]});
                v[B[i]].push_back({A[i], T[i]});
        }
        vector<pair<int, int>> X;
        for(int i = 0; i < N; i++){
                if(!used[i]){
                        val = 1e9;
                        dfs1(i, i);
                        dfs2(i, i);
                        X.push_back({val, v1});
                }
        }
        sort(X.rbegin(), X.rend());
        for(int i = 1; i < (int)X.size(); i++){
                v[X[0].second].push_back({X[i].second, L});
                v[X[i].second].push_back({X[0].second, L});
        }
        val = ve = 0;
        dfs(0, 0, 0);
        val = 0;
        dfs(ve, ve, 0);
        return val;
}

Compilation message

dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:32:22: warning: variable 'v2' set but not used [-Wunused-but-set-variable]
   32 |         int v1 = -1, v2 = -1;
      |                      ^~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 12100 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 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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