Submission #940300

#	Time	Username	Problem	Language	Result	Execution time	Memory
940300		vjudge1	꿈 (IOI13_dreaming)	C++17	Compilation error	0 ms	0 KiB

dreaming

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
#define int 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<pii> g[N];
int mxd[N], mxdu[N], used[N];

int dfs1(int v, int p){
    used[v] = 1;
    vector<int> ve = {};
    int cans = 0;
    for(auto e : g[v]){
        int 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);
}

int dfs2(int v, int p){
    used[v] = 1;
    multiset<int> ms;
    for(auto e : g[v]){
        int u = e.F, w = e.S;
        if(u != p){
            ms.insert(mxd[u] + w);
        }
    }
    int mx = infl;
    for(auto e : g[v]){
        int 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]});
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(!used[i]){
            ans = max(ans, dfs1(i, -1));
        }
    }
    memset(used, 0, sizeof used);
    multiset<int> ms;
    vector<int> rs = {};
    int dada[n];
    for(int i = 0; i < n; i++){
        if(!used[i]){
            dada[i] = dfs2(i, -1);
            rs.pb(i);
            ms.insert(dada[i]);
        }
    }
    int 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();
            int a = *it;
            it++;
            int 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';
}*/

Compilation message (stderr)

/usr/bin/ld: /tmp/ccYG6mdT.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status