Submission #1089271

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1089271	2024-09-16T08:55:34 Z	RiverFlow	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

void prepare(); void main_code();

int main() {
    ios::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);
    }
    const bool MULTITEST = 0; prepare();
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); }
}

void prepare(){};

int n, k;
vec<ii> g[N];
bool on[N];
int s[N];
void init(int u, int p) {
    s[u] = 1;
    for(auto [v,w] : g[u]) if (on[v] and v != p) {
        init(v, u);
        s[u] += s[v];
    }
}
int centroid(int u, int p, int t) {
    for(auto [v,w]:g[u])if(on[v] and v!=p and s[v]>t/2)
        return centroid(v,u,t);
    return u;
}

int ans = 0;

multiset<int> d[5 * N];

void DFS(int u, int par, bool t, int dis, int dx) {
    if (dis > k) return ;
    if (t == 0) {
        if (sz(d[k - dis])) {
            ans = min(ans, dx + *d[k - dis].begin());
        }
    } else if (t == 1) {
        d[dis].insert(dx);
    } else
        d[dis].erase(d[dis].find(dx));
    for(auto [v,w] : g[u]) if (v != par and on[v]) {
        DFS(v, u, t, dis + w, dx + 1);
    }
}
void calc(int u) {
    d[0].insert(0);
    for(auto [v,w] : g[u]) if (on[v]) {
        DFS(v,u,0,w, 1);
        DFS(v,u,1,w, 1);
    }
    for(auto [v,w] : g[u]) if (on[v]) {
        DFS(v,u,-1,w, 1);
    }
    d[0].erase(0);
}
void solve(int u) {
    init(u, 0);
    u = centroid(u, 0, s[u]);
    calc(u);
    on[u] = 0;
    for(auto [v,w] : g[u]) if (on[v]){
        solve(v);
    }
}
void main_code() {
    cin >> n >> k;
    ans = n + 1;
    FOR(i, 1, n) on[i] = 1;
    FOR(i, 2, n) {
        int u, v, w; cin >> u >> v >> w;
        ++u, ++v;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    solve(1);
    if (ans == n + 1) ans = -1;
    cout << ans;
}


/*     Let the river flows naturally     */

Compilation message

race.cpp: In function 'void init(int, int)':
race.cpp:52:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |     for(auto [v,w] : g[u]) if (on[v] and v != p) {
      |              ^
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:58:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     for(auto [v,w]:g[u])if(on[v] and v!=p and s[v]>t/2)
      |              ^
race.cpp: In function 'void DFS(int, int, bool, int, int)':
race.cpp:77:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |     for(auto [v,w] : g[u]) if (v != par and on[v]) {
      |              ^
race.cpp: In function 'void calc(int)':
race.cpp:83:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |     for(auto [v,w] : g[u]) if (on[v]) {
      |              ^
race.cpp:87:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |     for(auto [v,w] : g[u]) if (on[v]) {
      |              ^
race.cpp: In function 'void solve(int)':
race.cpp:97:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |     for(auto [v,w] : g[u]) if (on[v]){
      |              ^
race.cpp: In function 'int main()':
race.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccBGa0ub.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cczXY709.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cczXY709.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