oj.uz

Submission #998088

# Submission time Handle Problem Language Result Execution time Memory
998088 2024-06-13T09:35:41 Z Muhammet Dreaming (IOI13_dreaming) C++17
0 / 100
 152 ms 37664 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];
    if(sz(v1) >= 2) 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;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:63:40: warning: value computed is not used [-Wunused-value]
   63 |     if(sz(v1) >= 2) v1[sz(v1) - 1] + l + v1[sz(v1) - 2];

Subtask #1
0 / 14.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 27848 KB Output isn't correct
2 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 152 ms 37664 KB Output isn't correct
2 Halted 0 ms 0 KB -