Submission #953390

#	Time	Username	Problem	Language	Result	Execution time	Memory
953390		Lemser	Race (IOI11_race)	C++14	0 / 100	12 ms	30044 KiB

race

#include <bits/stdc++.h>
// #include "race.h"
#define endl '\n'
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define fo(i,n) for(auto i =0 ; i < n;i++)
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
using namespace std;
using ii = pair<int,int>; using ll = long long; using ull = unsigned long long;
using vi = vector<ll>;
void valid(int in){cout<<((in)?"YES\n":"NO\n");return;}
const int N = 1e6 + 7;
vector<ii> graph[N];
bool vis[N];int ans = 1e9, sz[N], mn[N],k;
void find_sz(int nodo ,int  p = -1){sz[nodo]=1;
    for(auto [v, cost] : graph[nodo]){if(v==p || vis[v] )continue;
        find_sz(v,nodo);
        sz[nodo] += sz[v];
    }
}
int find_cent(int nodo, int raiz, int p = -1){
    for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
        if(sz[v]>sz[raiz]/2)return find_cent(v, raiz, nodo);
    }return nodo;
}
void dfs_calc(int nodo, int sum = 0,int nivel = 0, int p = -1){
    // cout << nodo << " " << sum << " " << nivel << " " << p << endl;
    if(vis[nodo])return;if(sum>k)return;
    ans = min(ans, mn[k-sum]+ nivel);
    for(auto [v,cost] : graph[nodo]){if(v==p)continue;
        dfs_calc(v, sum + cost, nivel+1, nodo);
    }
}
void dfs_add(int nodo, int sum = 0,  int nivel = 0, int p = -1){
    if(vis[nodo])return;if(sum>k)return;
    mn[sum] = min(mn[sum],nivel);
    for(auto [v,cost] : graph[nodo]){if(v==p)continue;
        dfs_add(v, sum+cost, nivel+1, nodo);
    }
}
void dfs_del(int nodo, int sum = 0, int nivel = 0, int p = -1){
    if(vis[nodo])return;if(sum>k)return;mn[sum] =1e9;
    for(auto [v,cost] : graph[nodo]){if(v==p)continue;
        dfs_del(v, sum+cost, nivel+1, nodo);
    }
}
void solve(int nodo){if(vis[nodo])return;
    find_sz(nodo);int cen = find_cent(nodo,nodo);
    dfs_del(cen);mn[0]=0;
    // fo(i,k+2) cout << mn[i] << " "; cout << endl;
    for(auto [v,cost] : graph[cen]){
        dfs_calc(v, cost, 1,cen);
        dfs_add(v,cost, 1,cen);
    }vis[cen]=1;
    for(auto [v,cost] : graph[cen])solve(v);
}
int best_path(int n, int K, int H[][2], int L[]){k=K;fill(mn, mn+k+3, 1e9);
    fo(i,n-1){
        graph[H[i][0]].pb({H[i][1], L[i]});
        graph[H[i][1]].pb({H[i][0], L[i]});
    }solve(0);return (ans == 1e9 ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'void find_sz(int, int)':
race.cpp:25:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |     for(auto [v, cost] : graph[nodo]){if(v==p || vis[v] )continue;
      |              ^
race.cpp: In function 'int find_cent(int, int, int)':
race.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
      |              ^
race.cpp: In function 'void dfs_calc(int, int, int, int)':
race.cpp:37:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   37 |     if(vis[nodo])return;if(sum>k)return;
      |     ^~
race.cpp:37:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   37 |     if(vis[nodo])return;if(sum>k)return;
      |                         ^~
race.cpp:39:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     for(auto [v,cost] : graph[nodo]){if(v==p)continue;
      |              ^
race.cpp: In function 'void dfs_add(int, int, int, int)':
race.cpp:44:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   44 |     if(vis[nodo])return;if(sum>k)return;
      |     ^~
race.cpp:44:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |     if(vis[nodo])return;if(sum>k)return;
      |                         ^~
race.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |     for(auto [v,cost] : graph[nodo]){if(v==p)continue;
      |              ^
race.cpp: In function 'void dfs_del(int, int, int, int)':
race.cpp:51:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   51 |     if(vis[nodo])return;if(sum>k)return;mn[sum] =1e9;
      |     ^~
race.cpp:51:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   51 |     if(vis[nodo])return;if(sum>k)return;mn[sum] =1e9;
      |                         ^~
race.cpp:52:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |     for(auto [v,cost] : graph[nodo]){if(v==p)continue;
      |              ^
race.cpp: In function 'void solve(int)':
race.cpp:60:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     for(auto [v,cost] : graph[cen]){
      |              ^
race.cpp:64:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |     for(auto [v,cost] : graph[cen])solve(v);
      |              ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57