Submission #1112016

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1112016	2024-11-13T13:58:36 Z	CrabCNH	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

#include <bits/stdc++.h>

#define task   "brianthecrab"

#define int    long long
#define pii    pair <int, int>
#define fi     first
#define se     second
#define szf    sizeof
#define sz(s)  (int)((s).size())
#define all(v) (v).begin(), (v).end()

using namespace std;

template <class T> void mini (T &t, T f) {if (t > f) t = f;}
template <class T> void maxi (T &t, T f) {if (t < f) t = f;}

const int N = 1e6 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;

int n, k;
int tt;

struct CD {
    int sz[N], edgecnt[N], exist[N];
    set <pii> G[N];
    
    // get sz
    
    int dfs (int u, int p) {
        sz[u] = 1;
        for (auto [v, dis] : G[u]) {
            if (v == p) {
                continue;
            }
            sz[u] += dfs (v, u);
        }
        return sz[u];
    }
    
    // find centroid
        
    int centroid (int u, int p, int nn) {
        for (auto [v, dis] : G[u]) {
            if (v == p) {
                continue;
            }
            if (sz[v] > nn / 2) {
                return centroid (v, u, nn);
            }
        }
        return u;
    }
        
    int dfs2 (int u, int p, int d, int cnt, int t, vector <pii> &vv) {
        int want = k - d;
        int ans = inf;
        if (want >= 0 && exist[want] == t) {
            mini (ans, cnt + edgecnt[want]);
        }
        if (d <= k) {
            vv.push_back ({d, cnt});
            for (auto [v, dis] : G[u]) {
                if (v == p) {
                    continue;
                }
                int cur = dfs2 (v, u, d + dis, cnt + 1, t, vv);
                mini (ans, cur);
            }
        }
        return ans;
    }
    
    int sol (int u, int p) {
        int nn = dfs (u, p);
        int c = centroid (u, p, nn);
        int ans = inf;
        int t = ++t;
        exist[0] = t;
        edgecnt[0] = 0;
        for (auto [v, dis] : G[c]) {
            vector <pii> tmp;
            int cur = dfs2 (v, c, dis, 1, t, tmp);
            mini (ans, cur);
            for (auto [v1, dis1] : tmp) {
                if (exist[v1] != t || (exist[v1] == t && edgecnt[v1] > dis1)) {
                    exist[v1] = t;
                    edgecnt[v1] = dis1;
                }
            }
        }
        vector <pii> tmp (G[c].begin (), G[c].end ());
        for (auto [v, dis] : tmp) {
            G[c].erase ({v, dis});
            G[v].erase ({c, dis});
            int cur = sol (v, c);
            mini (ans, cur);
        }
        return ans;
    }
} T;

signed main () {
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    cout.tie (0);
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    cin >> n >> k;
    for (int i = 1; i <= n - 1; i ++) {
        int u, v, w;
        cin >> u >> v >> w;
        T.G[u].insert ({v, w});
        T.G[v].insert ({u, w});
    }
    tt = 0;
    int ans = T.sol (0, -1);
    cout << (ans == inf ? - 1 : ans);
    return 0;
}
// hmvncvdqdela

Compilation message

race.cpp: In member function 'long long int CD::dfs(long long int, long long int)':
race.cpp:33:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |         for (auto [v, dis] : G[u]) {
      |                   ^
race.cpp: In member function 'long long int CD::centroid(long long int, long long int, long long int)':
race.cpp:45:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |         for (auto [v, dis] : G[u]) {
      |                   ^
race.cpp: In member function 'long long int CD::dfs2(long long int, long long int, long long int, long long int, long long int, std::vector<std::pair<long long int, long long int> >&)':
race.cpp:64:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |             for (auto [v, dis] : G[u]) {
      |                       ^
race.cpp: In member function 'long long int CD::sol(long long int, long long int)':
race.cpp:79:17: warning: operation on 't' may be undefined [-Wsequence-point]
   79 |         int t = ++t;
      |                 ^~~
race.cpp:82:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |         for (auto [v, dis] : G[c]) {
      |                   ^
race.cpp:86:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |             for (auto [v1, dis1] : tmp) {
      |                       ^
race.cpp:94:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |         for (auto [v, dis] : tmp) {
      |                   ^
race.cpp: In function 'int main()':
race.cpp:109:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:110:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp: In member function 'long long int CD::sol(long long int, long long int)':
race.cpp:79:19: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |         int t = ++t;
      |                   ^
/usr/bin/ld: /tmp/ccbD4us5.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccNDppj6.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccNDppj6.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status