oj.uz

Submission #997931

# Submission time Handle Problem Language Result Execution time Memory
997931 2024-06-13T06:53:50 Z Muhammet Dreaming (IOI13_dreaming) C++17
0 / 100
 141 ms 37492 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;

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,p[x].back());
    for(auto i : v[x]){
        if(vi[i.ff] == 0){
            ll y = p[x].back();
            if(y == p[i.ff].back() + i.ss) y = p[x][sz(p[x]) - 2];
            p[i.ff].push_back(y + i.ss);
            sort(p[i.ff].begin(), p[i.ff].end());
            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] + 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 141 ms 37492 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 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 27852 KB Output is correct
2 Correct 71 ms 28108 KB Output is correct
3 Correct 71 ms 27792 KB Output is correct
4 Correct 73 ms 28108 KB Output is correct
5 Correct 74 ms 27844 KB Output is correct
6 Correct 96 ms 29644 KB Output is correct
7 Correct 70 ms 28784 KB Output is correct
8 Correct 67 ms 27596 KB Output is correct
9 Correct 66 ms 27456 KB Output is correct
10 Correct 72 ms 28872 KB Output is correct
11 Correct 2 ms 10844 KB Output is correct
12 Correct 32 ms 27076 KB Output is correct
13 Correct 33 ms 27088 KB Output is correct
14 Correct 42 ms 27080 KB Output is correct
15 Correct 33 ms 27108 KB Output is correct
16 Correct 34 ms 27288 KB Output is correct
17 Correct 33 ms 27264 KB Output is correct
18 Correct 33 ms 27088 KB Output is correct
19 Correct 37 ms 27220 KB Output is correct
20 Incorrect 2 ms 10588 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 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

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