Submission #333929

#	Time	Username	Problem	Language	Result	Execution time	Memory
333929		theshadow_04	Dreaming (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KiB

dreaming

// V T AN
#include <bits/stdc++.h>
#define Task "dreaming"
#define F first
#define S second
#define pb push_back

using namespace std;

const int maxn = 100005;

int n, m, l;
vector<pair<int, int> > ke[maxn];
int dd[maxn], tr[maxn], cnt;
vector<int> tplt[maxn];
long long ans[maxn], d[maxn], Max = -1, pos = -1;

void DFS_tplt(int u) {
    for(auto p : ke[u]) {
        int v = p.F, w = p.S;
        if(dd[v]) continue;
        dd[v] = 1;
        tplt[cnt].pb(v);
        d[v] = max(d[v], d[u] + w);
        DFS_tplt(v);
    }
}

void DFS(int u, int par) {
    for(auto p : ke[u]) {
        int v = p.F, w = p.S;
        if(v == par) continue;
        d[v] = max(d[v], d[u] + w);
        tr[v] = u;
        DFS(v, u);
    }
}

void Center_node(int s) {
    int mx = -1, be = -1;
    tplt[++cnt].pb(s);
    dd[s] = 1;
    DFS_tplt(s);
    if(tplt[cnt].size() == 1) {
        ans[cnt] = 0;
        return;
    }
    for(auto i : tplt[cnt]) {
        if(d[i] > mx) mx = d[i], be = i;
    }
    for(auto x : tplt[cnt]) d[x] = 0;
    DFS(be, be);
    int mx2 = -1, en = -1;
    for(auto i : tplt[cnt]) {
        if(d[i] > mx2) mx2 = d[i], en = i;
    }
    ans[cnt] = 1e18;
    int u = en;
    while(u != be) {
        ans[cnt] = min(ans[cnt], max(d[u], d[en] - d[u]));
        u = tr[u];
    }
    if(ans[cnt] > Max) {
        Max = ans[cnt];
        pos = cnt;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);
	if(fopen(Task".inp", "r")){
		freopen(Task".inp", "r", stdin);
		freopen(Task".out", "w", stdout);
	}
    cin >> n >> m >> l;
    for(int i = 1; i <= m; ++ i) {
        int u, v, w;
        cin >> u >> v >> w;
//        ++ u, ++ v;
        ke[u].pb({v, w});
        ke[v].pb({u, w});
    }
    for(int i = 1; i <= n; ++ i) if(!dd[i]){
        Center_node(i);
    }
    long long res = 0;
    for(int i = 1; i <= cnt; ++ i) {
        if(i != pos) {
            res = max(res, ans[pos] + ans[i] + l);
        }
    }
    cout << res;
}

// CHY_AKAV

Compilation message (stderr)

dreaming.cpp: In function 'int main()':
dreaming.cpp:73:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   73 |   freopen(Task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:74:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   74 |   freopen(Task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/cc2ixn74.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccU31krB.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccU31krB.o: In function `main':
grader.c:(.text.startup+0xc9): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status