Submission #694744

#	Time	Username	Problem	Language	Result	Execution time	Memory
694744		hgmhc	Dreaming (IOI13_dreaming)	C++17	Compilation error	0 ms	0 KiB

dreaming

// 디버깅 오래 걸린 이유 및 반성:
// tree dp에서는 visited를 잘 검사하더라도 부모 노드로 다시 올라가는 경우가 없도록 e를 항상 설정해주도록 하자.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define dbg(x) cerr << #x << ": " << x << '\n'
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int N = 1e5+3, M = N;
int n, m, l;
ll dp[N];
vector<ii> adj[N];
bool vis[N];

void dfs1(int s, int e = 0) {
    for (auto [u,w] : adj[s]) if (u != e) {
        dfs1(u,s), Mup(dp[s],dp[u]+w);
    }
}
ll x, ans;
void dfs2(int s, int e = 0, ll v = 0) {
    if (vis[s]) return;
    vis[s] = true;
    ll mx1 = 0, mx2 = 0;
    int fr = 0;
    for (auto [u,w] : adj[s]) if (u != e) {
        if (mx1 < dp[u]+w) {
            mx2 = mx1;
            mx1 = dp[u]+w, fr = u;
        } else if (mx2 < dp[u]+w) {
            mx2 = dp[u]+w;
        }
    }
    Mup(dp[s],v);
    mup(x,dp[s]);
    Mup(ans,dp[s]);
    for (auto [u,w] : adj[s]) if (u != e) {
        if (fr != u) dfs2(u,s,max(v,mx1)+w);
        else dfs2(u,s,max(v,mx2)+w);
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &l);
    rep(i,1,m) {
        int a, b, t;
        scanf("%d %d %d", &a, &b, &t);
        adj[a].push_back({b,t});
        adj[b].push_back({a,t});
    }
    vector<ll> v;
    rep(i,0,n-1) if (not vis[i]) {
        x = 1e18, dfs1(i), dfs2(i);
        v.push_back(x);
    }
    sort(v.rbegin(),v.rend());
    if (siz(v) == 1) Mup(ans,v[0]);
    else if (siz(v) == 2) Mup(ans,v[0]+l+v[1]);
    else Mup(ans,max(v[0]+l+v[1],v[1]+l+l+v[2]));
    printf("%lld", ans);
}

Compilation message (stderr)

dreaming.cpp: In function 'int main()':
dreaming.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d %d %d", &n, &m, &l);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%d %d %d", &a, &b, &t);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccyGbY9x.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccv9hCIx.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccv9hCIx.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status