Submission #971813

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
971813	2024-04-29T10:48:06 Z	khanhtb	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 998244353;
const ll inf = 1e18;
const ll base = 26;
const ll blocksz = 320;
const ll N = 1e6+8;
const ll lim = 1e5+8;
ll tin[N],tout[N],tdfs,d[N],sz[N],euler[N],ans = inf,n,k,h[N];
map<ll,ll> mn;
vpll g[N];
void init(ll u, ll p){
    sz[u] = 1;
    tin[u] = ++tdfs;
    euler[tdfs] = u;
    for(auto [v,w]:g[u]){
        if(v == p) continue;
        h[v] = h[u]+1;
        d[v] = d[u]+w;
        if(d[v] == k) ans = min(ans,h[v]);
        init(v,u);
        sz[u] += sz[v];
    }
    tout[u] = tdfs;
}
void sackadd(ll u){
    if(!mn[d[u]]) mn[d[u]] = inf;
    mn[d[u]] = min(mn[d[u]],h[u]);
}
void sackrmv(ll u){
    mn[d[u]] = inf;
}
void dfs(ll u, ll p){
    ll big = 0;
    for(auto [v,w]:g[u]){
        if(v == p) continue;
        if(sz[v] > sz[big]) big = v;
    }
    for(auto [v,w]:g[u]){
        if(v != p && v != big){
            dfs(v,u);
            for(ll i = tin[v]; i <= tout[v]; i++) sackrmv(euler[i]);
        }
    }
    if(big) dfs(big,u);
    if(!mn[d[u]+k]) mn[d[u]+k] = inf;
    ans = min(ans,mn[d[u]+k]-h[u]);
    sackadd(u);
    for(auto [v,w]:g[u]){
        if(v == big || v == p) continue;
        for(ll i = tin[v]; i <= tout[v]; i++){
            ll ch = euler[i];
            ll len = k-d[ch]+2*d[u];
            if(len < 0) continue;
            if(!mn[len]) mn[len] = inf;
            ans = min(ans,mn[len]+h[ch]-2*h[u]);
        }
        for(ll i = tin[v]; i <= tout[v]; i++){
            ll ch = euler[i];
            sackadd(ch);
        }
    }
}
void solve(){
    cin >> n >> k;
    for(ll i = 1; i < n; i++){
        ll u,v,w;cin >> u >> v >> w;
        u++,v++;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    init(1,1);
    dfs(1,1);
    cout << ((ans >= 2e5)?-1:ans);
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    if(fopen("test.inp","r")){
		freopen("test.inp","r",stdin);	
    	freopen("test.out","w",stdout);
	}
    int T = 1;
    // cin >> T;
    for(int tt = 1; tt <= T; tt++){
    	solve();
    	// cout << '\n';
    }
}

Compilation message

race.cpp: In function 'void init(long long int, long long int)':
race.cpp:28:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |     for(auto [v,w]:g[u]){
      |              ^
race.cpp: In function 'void dfs(long long int, long long int)':
race.cpp:47:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for(auto [v,w]:g[u]){
      |              ^
race.cpp:51:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for(auto [v,w]:g[u]){
      |              ^
race.cpp:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for(auto [v,w]:g[u]){
      |              ^
race.cpp: In function 'int main()':
race.cpp:91:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   freopen("test.inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
race.cpp:92:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |      freopen("test.out","w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccUKaSuG.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccSOTdiF.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccSOTdiF.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