oj.uz

Submission #1003026

# Submission time Handle Problem Language Result Execution time Memory
1003026 2024-06-20T02:46:53 Z tamir1 Dreaming (IOI13_dreaming) C++17
18 / 100
 173 ms 38996 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
 
#define N 200005
#define ff first
#define sz(s) (int)s.size()
#define ss second
#define ll long long
 
vector <pair<ll,ll>> v[N], p[N];
 
vector <ll> v1;
 
map <ll,bool> vis, vi;
 
ll mn, f[N];
 
ll dfs(ll x){
    vis[x] = 1;
    for(auto i : v[x]){
        if(vis[i.ff] == 0){
            p[x].push_back({dfs(i.ff) + i.ss, i.ff});
        }
    }
    p[x].push_back({0,-1});
    sort(p[x].begin(), p[x].end());
    return p[x].back().ff;
}
 
void df(ll x){
    vi[x] = 1;
    mn = min(mn,max(p[x].back().ff,f[x]));
    for(auto i : v[x]){
        if(vi[i.ff] == 0){
            ll y = p[x].back().ff;
            if(p[x].back().ss == i.ff) y = p[x][sz(p[x]) - 2].ff;
            f[i.ff] = (max(y,f[x]) + i.ss);
        }
    }
    for(auto i : v[x]){
        if(vi[i.ff] == 0) df(i.ff);
    }
    return;
}
 
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    vis.clear();
    v1.clear();
    vi.clear();
    for(int i = 0; i < n; i++){
        v[i].clear();
        p[i].clear();
        f[i] = 0;
    }
 
    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]});
    }
 
    for(int i = 0; i < n; i++){
        if(vis[i] == 0){
            dfs(i);
            mn = INT_MAX;
            df(i);
            v1.push_back(mn);
        }
    }
    sort(v1.begin(), v1.end());
    ll k = v1.back();
    if(sz(v1) >= 2) k = max(k,v1.back() + l + v1[sz(v1) - 2]);
    if(sz(v1) >= 3) k = max(k, v1[sz(v1) - 3] + l*2 + v1[sz(v1) - 2]);
    return k;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 28844 KB Output is correct
2 Correct 83 ms 28860 KB Output is correct
3 Correct 82 ms 28752 KB Output is correct
4 Correct 81 ms 28876 KB Output is correct
5 Correct 88 ms 28876 KB Output is correct
6 Correct 83 ms 30412 KB Output is correct
7 Correct 83 ms 29640 KB Output is correct
8 Correct 80 ms 28416 KB Output is correct
9 Correct 89 ms 28360 KB Output is correct
10 Correct 87 ms 29640 KB Output is correct
11 Correct 4 ms 9820 KB Output is correct
12 Correct 39 ms 27088 KB Output is correct
13 Correct 39 ms 27076 KB Output is correct
14 Correct 38 ms 26900 KB Output is correct
15 Correct 38 ms 27068 KB Output is correct
16 Correct 43 ms 27080 KB Output is correct
17 Correct 40 ms 27088 KB Output is correct
18 Correct 41 ms 27100 KB Output is correct
19 Correct 38 ms 27076 KB Output is correct
20 Correct 4 ms 9816 KB Output is correct
21 Correct 5 ms 9816 KB Output is correct
22 Correct 5 ms 10328 KB Output is correct
23 Correct 39 ms 27048 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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