oj.uz

답안 #998516

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
998516 2024-06-14T06:26:45 Z Muhammet 꿈 (IOI13_dreaming) C++17
0 / 100
 137 ms 59588 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) 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 < n; i++) v[i].clear(), f[i] = 0;
    vis.clear();
    vi.clear();
    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);
            // cout << i << ' ' << mn << '\n';
        }
    }

    sort(v1.begin(), v1.end());
    assert(v1.size() == 2);
    return v1.back() + l + v1[sz(v1) - 2];
    // 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]);

    // for(int i = 0; i < n; i++) cout << i << ' ' << f[i] << ' ' << p[i].back() << '\n';

    // return k;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 137 ms 37712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 12380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 137 ms 37712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 90 ms 59588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 12380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 137 ms 37712 KB Output isn't correct
2 Halted 0 ms 0 KB -