oj.uz

Submission #998133

# Submission time Handle Problem Language Result Execution time Memory
998133 2024-06-13T10:18:13 Z Muhammet Dreaming (IOI13_dreaming) C++17
18 / 100
 153 ms 37676 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];

vector <ll> p[N], 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);
        }
    }
    p[x].push_back(0);
    sort(p[x].begin(), p[x].end());
    return p[x].back();
}

void df(ll x){
    vi[x] = 1;
    mn = min(mn,max(p[x].back(),f[x]));
    for(auto i : v[x]){
        if(vi[i.ff] == 0){
            ll y = p[x].back();
            if(y == p[i.ff].back() + i.ss){
                if(sz(p[x]) == 1) y = 0;
                else {
                    y = p[x][sz(p[x]) - 2];
                }
            }
            f[i.ff] = (max(y,f[x]) + i.ss);
            df(i.ff);
        }
    }
    return;
}

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]});
    }
    for(int i = 0; i < n; i++){
        if(vis[i] == 0){
            dfs(i);
            mn = 1e9;
            df(i);
            v1.push_back(mn);
        }
    }

    sort(v1.begin(), v1.end());

    ll k = v1[sz(v1) - 1];
    if(sz(v1) >= 2) k = max(k,v1[sz(v1) - 1] + 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 153 ms 37676 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 12380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 37676 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 79 ms 29640 KB Output is correct
2 Correct 71 ms 29644 KB Output is correct
3 Correct 71 ms 29588 KB Output is correct
4 Correct 70 ms 29644 KB Output is correct
5 Correct 71 ms 29528 KB Output is correct
6 Correct 84 ms 31076 KB Output is correct
7 Correct 73 ms 30408 KB Output is correct
8 Correct 72 ms 29132 KB Output is correct
9 Correct 70 ms 29184 KB Output is correct
10 Correct 76 ms 30408 KB Output is correct
11 Correct 2 ms 12376 KB Output is correct
12 Correct 35 ms 28704 KB Output is correct
13 Correct 37 ms 28844 KB Output is correct
14 Correct 33 ms 28612 KB Output is correct
15 Correct 35 ms 28880 KB Output is correct
16 Correct 34 ms 28624 KB Output is correct
17 Correct 35 ms 28852 KB Output is correct
18 Correct 35 ms 28868 KB Output is correct
19 Correct 40 ms 28624 KB Output is correct
20 Correct 2 ms 10328 KB Output is correct
21 Correct 2 ms 10332 KB Output is correct
22 Correct 4 ms 12892 KB Output is correct
23 Correct 33 ms 28616 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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