oj.uz

Submission #953405

# Submission time Handle Problem Language Result Execution time Memory
953405 2024-03-26T00:16:43 Z Lemser Race (IOI11_race) C++14
100 / 100
 317 ms 57680 KB 
#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){if(sum>k)return;
    ans = min(ans, mn[k-sum]+ nivel);
    for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
        dfs_calc(v, sum + cost, nivel+1, nodo);
    }
}
void dfs_add(int nodo, int sum = 0,  int nivel = 0, int p = -1){if(sum>k)return;
    mn[sum] = min(mn[sum],nivel);
    for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
        dfs_add(v, sum+cost, nivel+1, nodo);
    }
}
void dfs_del(int nodo, int sum = 0, int nivel = 0, int p = -1){
    if(sum>k)return;mn[sum] =1e9;
    for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])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);mn[0]=0;
    for(auto [v,cost] : graph[cen]){if(vis[v])continue;
        dfs_calc(v, cost, 1,cen);
        dfs_add(v,cost, 1,cen);
    }dfs_del(cen);vis[cen]=1;
    for(auto [v,cost] : graph[cen])if(!vis[v])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

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:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |     for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
      |              ^
race.cpp: In function 'void dfs_add(int, int, int, int)':
race.cpp:43:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
      |              ^
race.cpp: In function 'void dfs_del(int, int, int, int)':
race.cpp:48:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |     if(sum>k)return;mn[sum] =1e9;
      |     ^~
race.cpp:48:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   48 |     if(sum>k)return;mn[sum] =1e9;
      |                     ^~
race.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for(auto [v,cost] : graph[nodo]){if(v==p || vis[v])continue;
      |              ^
race.cpp: In function 'void solve(int)':
race.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for(auto [v,cost] : graph[cen]){if(vis[v])continue;
      |              ^
race.cpp:59:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |     for(auto [v,cost] : graph[cen])if(!vis[v])solve(v);
      |              ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 30044 KB Output is correct
2 Correct 7 ms 30044 KB Output is correct
3 Correct 8 ms 30580 KB Output is correct
4 Correct 6 ms 30044 KB Output is correct
5 Correct 7 ms 30044 KB Output is correct
6 Correct 6 ms 30044 KB Output is correct
7 Correct 6 ms 30044 KB Output is correct
8 Correct 7 ms 30044 KB Output is correct
9 Correct 7 ms 30044 KB Output is correct
10 Correct 7 ms 30192 KB Output is correct
11 Correct 7 ms 30044 KB Output is correct
12 Correct 7 ms 30044 KB Output is correct
13 Correct 7 ms 30040 KB Output is correct
14 Correct 8 ms 30040 KB Output is correct
15 Correct 7 ms 30296 KB Output is correct
16 Correct 6 ms 30160 KB Output is correct
17 Correct 7 ms 30040 KB Output is correct
18 Correct 7 ms 30044 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 30044 KB Output is correct
2 Correct 7 ms 30044 KB Output is correct
3 Correct 8 ms 30580 KB Output is correct
4 Correct 6 ms 30044 KB Output is correct
5 Correct 7 ms 30044 KB Output is correct
6 Correct 6 ms 30044 KB Output is correct
7 Correct 6 ms 30044 KB Output is correct
8 Correct 7 ms 30044 KB Output is correct
9 Correct 7 ms 30044 KB Output is correct
10 Correct 7 ms 30192 KB Output is correct
11 Correct 7 ms 30044 KB Output is correct
12 Correct 7 ms 30044 KB Output is correct
13 Correct 7 ms 30040 KB Output is correct
14 Correct 8 ms 30040 KB Output is correct
15 Correct 7 ms 30296 KB Output is correct
16 Correct 6 ms 30160 KB Output is correct
17 Correct 7 ms 30040 KB Output is correct
18 Correct 7 ms 30044 KB Output is correct
19 Correct 6 ms 30044 KB Output is correct
20 Correct 6 ms 30044 KB Output is correct
21 Correct 7 ms 30164 KB Output is correct
22 Correct 9 ms 32088 KB Output is correct
23 Correct 8 ms 32092 KB Output is correct
24 Correct 8 ms 32092 KB Output is correct
25 Correct 7 ms 32204 KB Output is correct
26 Correct 8 ms 32092 KB Output is correct
27 Correct 7 ms 32092 KB Output is correct
28 Correct 8 ms 32092 KB Output is correct
29 Correct 7 ms 32312 KB Output is correct
30 Correct 7 ms 32088 KB Output is correct
31 Correct 7 ms 32088 KB Output is correct
32 Correct 8 ms 32092 KB Output is correct
33 Correct 8 ms 32256 KB Output is correct
34 Correct 7 ms 32092 KB Output is correct
35 Correct 8 ms 32328 KB Output is correct
36 Correct 8 ms 32092 KB Output is correct
37 Correct 7 ms 32092 KB Output is correct
38 Correct 8 ms 32080 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 30044 KB Output is correct
2 Correct 7 ms 30044 KB Output is correct
3 Correct 8 ms 30580 KB Output is correct
4 Correct 6 ms 30044 KB Output is correct
5 Correct 7 ms 30044 KB Output is correct
6 Correct 6 ms 30044 KB Output is correct
7 Correct 6 ms 30044 KB Output is correct
8 Correct 7 ms 30044 KB Output is correct
9 Correct 7 ms 30044 KB Output is correct
10 Correct 7 ms 30192 KB Output is correct
11 Correct 7 ms 30044 KB Output is correct
12 Correct 7 ms 30044 KB Output is correct
13 Correct 7 ms 30040 KB Output is correct
14 Correct 8 ms 30040 KB Output is correct
15 Correct 7 ms 30296 KB Output is correct
16 Correct 6 ms 30160 KB Output is correct
17 Correct 7 ms 30040 KB Output is correct
18 Correct 7 ms 30044 KB Output is correct
19 Correct 92 ms 36176 KB Output is correct
20 Correct 87 ms 36180 KB Output is correct
21 Correct 103 ms 36028 KB Output is correct
22 Correct 85 ms 36180 KB Output is correct
23 Correct 53 ms 36432 KB Output is correct
24 Correct 43 ms 36180 KB Output is correct
25 Correct 98 ms 40016 KB Output is correct
26 Correct 81 ms 43416 KB Output is correct
27 Correct 116 ms 42004 KB Output is correct
28 Correct 164 ms 56404 KB Output is correct
29 Correct 172 ms 55456 KB Output is correct
30 Correct 110 ms 42248 KB Output is correct
31 Correct 113 ms 42140 KB Output is correct
32 Correct 120 ms 42264 KB Output is correct
33 Correct 152 ms 40940 KB Output is correct
34 Correct 109 ms 41040 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 30044 KB Output is correct
2 Correct 7 ms 30044 KB Output is correct
3 Correct 8 ms 30580 KB Output is correct
4 Correct 6 ms 30044 KB Output is correct
5 Correct 7 ms 30044 KB Output is correct
6 Correct 6 ms 30044 KB Output is correct
7 Correct 6 ms 30044 KB Output is correct
8 Correct 7 ms 30044 KB Output is correct
9 Correct 7 ms 30044 KB Output is correct
10 Correct 7 ms 30192 KB Output is correct
11 Correct 7 ms 30044 KB Output is correct
12 Correct 7 ms 30044 KB Output is correct
13 Correct 7 ms 30040 KB Output is correct
14 Correct 8 ms 30040 KB Output is correct
15 Correct 7 ms 30296 KB Output is correct
16 Correct 6 ms 30160 KB Output is correct
17 Correct 7 ms 30040 KB Output is correct
18 Correct 7 ms 30044 KB Output is correct
19 Correct 6 ms 30044 KB Output is correct
20 Correct 6 ms 30044 KB Output is correct
21 Correct 7 ms 30164 KB Output is correct
22 Correct 9 ms 32088 KB Output is correct
23 Correct 8 ms 32092 KB Output is correct
24 Correct 8 ms 32092 KB Output is correct
25 Correct 7 ms 32204 KB Output is correct
26 Correct 8 ms 32092 KB Output is correct
27 Correct 7 ms 32092 KB Output is correct
28 Correct 8 ms 32092 KB Output is correct
29 Correct 7 ms 32312 KB Output is correct
30 Correct 7 ms 32088 KB Output is correct
31 Correct 7 ms 32088 KB Output is correct
32 Correct 8 ms 32092 KB Output is correct
33 Correct 8 ms 32256 KB Output is correct
34 Correct 7 ms 32092 KB Output is correct
35 Correct 8 ms 32328 KB Output is correct
36 Correct 8 ms 32092 KB Output is correct
37 Correct 7 ms 32092 KB Output is correct
38 Correct 8 ms 32080 KB Output is correct
39 Correct 92 ms 36176 KB Output is correct
40 Correct 87 ms 36180 KB Output is correct
41 Correct 103 ms 36028 KB Output is correct
42 Correct 85 ms 36180 KB Output is correct
43 Correct 53 ms 36432 KB Output is correct
44 Correct 43 ms 36180 KB Output is correct
45 Correct 98 ms 40016 KB Output is correct
46 Correct 81 ms 43416 KB Output is correct
47 Correct 116 ms 42004 KB Output is correct
48 Correct 164 ms 56404 KB Output is correct
49 Correct 172 ms 55456 KB Output is correct
50 Correct 110 ms 42248 KB Output is correct
51 Correct 113 ms 42140 KB Output is correct
52 Correct 120 ms 42264 KB Output is correct
53 Correct 152 ms 40940 KB Output is correct
54 Correct 109 ms 41040 KB Output is correct
55 Correct 13 ms 30552 KB Output is correct
56 Correct 14 ms 30556 KB Output is correct
57 Correct 62 ms 36388 KB Output is correct
58 Correct 33 ms 36336 KB Output is correct
59 Correct 80 ms 45452 KB Output is correct
60 Correct 284 ms 57680 KB Output is correct
61 Correct 123 ms 42328 KB Output is correct
62 Correct 138 ms 44396 KB Output is correct
63 Correct 170 ms 44112 KB Output is correct
64 Correct 317 ms 44112 KB Output is correct
65 Correct 121 ms 42164 KB Output is correct
66 Correct 240 ms 54872 KB Output is correct
67 Correct 76 ms 44484 KB Output is correct
68 Correct 175 ms 44456 KB Output is correct
69 Correct 174 ms 44368 KB Output is correct
70 Correct 156 ms 44204 KB Output is correct