제출 #940303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
940303		vjudge1	꿈 (IOI13_dreaming)	C++17	컴파일 에러	0 ms	0 KiB

dreaming

#include <bits/stdc++.h>
#include"dreaming.h

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"

const ld PI = 3.1415926535;
const int N = 100000+1;
const int M = 7e6 + 1;
int mod = 998244353;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;

vector<pll> g[N];
ll mxd[N], mxdu[N], used[N];

ll dfs1(int v, int p){
    used[v] = 1;
    vector<ll> ve = {};
    ll cans = 0;
    for(auto e : g[v]){
        ll u = e.F, w = e.S;
        if(u != p){
            cans = max(cans, dfs1(u, v));
            ve.pb(mxd[u] + w);
        }
    }
    sort(all(ve));
    reverse(all(ve));
    if(sz(ve) == 0){
        mxd[v] = 0;
        return cans;
    }
    mxd[v] = ve[0];
    if(sz(ve) == 1){
        return max(ve[0], cans);
    }
    return max(ve[1] + ve[0], cans);
}

ll dfs2(int v, int p){
    used[v] = 1;
    multiset<ll> ms;
    for(auto e : g[v]){
        ll u = e.F, w = e.S;
        if(u != p){
            ms.insert(mxd[u] + w);
        }
    }
    ll mx = infl;
    for(auto e : g[v]){
        ll u = e.F, w = e.S;
        if(u != p){
            ms.erase(ms.find(mxd[u] + w));
            if(sz(ms) > 0)
                mxdu[u] = max(mxdu[v] + w, *ms.rbegin() + w);
            else
                mxdu[u] = mxdu[v] + w;
            ms.insert(mxd[u] + w);
            mx = min(mx, dfs2(u, v));
        }
    }
    return min(mx, max(mxd[v], mxdu[v]));
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]){
    for(int i = 1; i <= m; i++){
        g[a[i - 1]].pb({b[i - 1], t[i - 1]});
        g[b[i - 1]].pb({a[i - 1], t[i - 1]});
    }
    ll ans = 0;
    for(int i = 0; i < n; i++){
        if(!used[i]){
            ans = max(ans, dfs1(i, -1));
        }
    }
    memset(used, 0, sizeof used);
    multiset<ll> ms;
    vector<ll> rs = {};
    ll dada[n];
    for(int i = 0; i < n; i++){
        if(!used[i]){
            dada[i] = dfs2(i, -1);
            rs.pb(i);
            ms.insert(dada[i]);
        }
    }
    ll ret = infl;
    for(auto v : rs){
        ms.erase(ms.find(dada[v]));
        if(sz(ms) == 0)
            return ans;
        if(sz(ms) == 1){
            ret = min(ret, max(ans, *ms.rbegin() + dada[v] + l));
        }else{
            auto it = ms.rbegin();
            ll a = *it;
            it++;
            ll b = *it;
            ret = min(ret, max(ans, max(*ms.rbegin() + dada[v] + l, a + b + 2 * l)));
        }
        ms.insert(dada[v]);
    }
    return ret;
}

/*signed main(){
    int n, m, l;
    cin >> n >> m >> l;
    int a[m], b[m], t[m];
    for(int i = 0; i < m; i++)
        cin >> a[i] >> b[i] >> t[i];
    cout << travelTime(n, m, l, a, b, t) << '\n';
}*/

컴파일 시 표준 에러 (stderr) 메시지

dreaming.cpp:2:9: warning: missing terminating " character
    2 | #include"dreaming.h
      |         ^
dreaming.cpp:2:9: error: #include expects "FILENAME" or <FILENAME>
    2 | #include"dreaming.h
      |         ^~~~~~~~~~~