oj.uz

Submission #185274

# Submission time Handle Problem Language Result Execution time Memory
185274 2020-01-11T09:59:57 Z awlintqaa Race (IOI11_race) C++14
100 / 100
 788 ms 37368 KB 
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 500
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1000000007;//998244353;
const ll inf=1e18*4;
const ld pai=acos(-1);
#include "race.h"
int n,k,ans=1e9;
vpi v[200009];
int from[1000009];
int sz[200009],done[200009],P[200009];
vpi all,ret;
void dfssz(int node,int p){
        P[node]=p;
        sz[node]=1;
        for(auto u:v[node]){
                if(u.fi==p)C;
                if(done[u.fi])C;
                dfssz(u.fi,node);
                sz[node]+=sz[u.fi];
        }
}
void dfs(int node,int p,int t,int num){
        if(t>k)return ;
        ans=min(ans,from[k-t]+num);
        ret.pb({t,num});
        all.pb({t,num});
        for(auto u:v[node]){
                if(done[u.fi] || u.fi==p)C;
                dfs(u.fi,node,t+u.se,num+1);
        }
}
void solve(int node){
        ret.clear();
        all.clear();
        for(auto u: v[node]){
                if(done[u.fi])C;
                dfs(u.fi,u.fi,u.se,1);
                for(auto x:ret){
                        from[x.fi]=min(from[x.fi],x.se);
                }
                ret.clear();
        }
}
void erase(){
        for(auto u:all)from[u.fi]=1e9;
        all.clear();
}
void create(int start){
        dfssz(start,start);
        queue<int>q;q.push(start);
        int best=1e9,who=-1;
        while(q.size()){
                int node=q.front();q.pop();
                int s=sz[start]-sz[node];
                for(auto u :v[node]){
                        if(done[u.fi] || P[node]==u.fi)C;
                        q.push(u.fi);
                        s=max(s,sz[u.fi]);
                }
                if(s<best)best=s,who=node;
        }
        done[who]=1;
        solve(who);
        erase();
        for(auto u: v[who]){
                if(done[u.fi])C;
                create(u.fi);
        }
}
int best_path(int N, int K, int H[][2], int L[]){
        n=N,k=K;
        for(int i=0;i<n-1;i++){
                int a,b,c;
                a=H[i][0],b=H[i][1],c=L[i];
                v[a].pb({b,c});
                v[b].pb({a,c});
        }
        for(int i=1;i<=1e6;i++)from[i]=1e9;
        create(0);
        if(ans==1e9)return -1;
        return ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8952 KB Output is correct
2 Correct 10 ms 8952 KB Output is correct
3 Correct 10 ms 8952 KB Output is correct
4 Correct 11 ms 8952 KB Output is correct
5 Correct 10 ms 8956 KB Output is correct
6 Correct 10 ms 8952 KB Output is correct
7 Correct 10 ms 8952 KB Output is correct
8 Correct 10 ms 8952 KB Output is correct
9 Correct 10 ms 8952 KB Output is correct
10 Correct 10 ms 8952 KB Output is correct
11 Correct 12 ms 8952 KB Output is correct
12 Correct 10 ms 8952 KB Output is correct
13 Correct 10 ms 8952 KB Output is correct
14 Correct 10 ms 8952 KB Output is correct
15 Correct 10 ms 8952 KB Output is correct
16 Correct 10 ms 8940 KB Output is correct
17 Correct 10 ms 8956 KB Output is correct
18 Correct 10 ms 8952 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8952 KB Output is correct
2 Correct 10 ms 8952 KB Output is correct
3 Correct 10 ms 8952 KB Output is correct
4 Correct 11 ms 8952 KB Output is correct
5 Correct 10 ms 8956 KB Output is correct
6 Correct 10 ms 8952 KB Output is correct
7 Correct 10 ms 8952 KB Output is correct
8 Correct 10 ms 8952 KB Output is correct
9 Correct 10 ms 8952 KB Output is correct
10 Correct 10 ms 8952 KB Output is correct
11 Correct 12 ms 8952 KB Output is correct
12 Correct 10 ms 8952 KB Output is correct
13 Correct 10 ms 8952 KB Output is correct
14 Correct 10 ms 8952 KB Output is correct
15 Correct 10 ms 8952 KB Output is correct
16 Correct 10 ms 8940 KB Output is correct
17 Correct 10 ms 8956 KB Output is correct
18 Correct 10 ms 8952 KB Output is correct
19 Correct 10 ms 8952 KB Output is correct
20 Correct 10 ms 8952 KB Output is correct
21 Correct 11 ms 9080 KB Output is correct
22 Correct 11 ms 9080 KB Output is correct
23 Correct 11 ms 8956 KB Output is correct
24 Correct 11 ms 8952 KB Output is correct
25 Correct 11 ms 9080 KB Output is correct
26 Correct 12 ms 8952 KB Output is correct
27 Correct 11 ms 8952 KB Output is correct
28 Correct 11 ms 9080 KB Output is correct
29 Correct 12 ms 9080 KB Output is correct
30 Correct 12 ms 9012 KB Output is correct
31 Correct 11 ms 9080 KB Output is correct
32 Correct 11 ms 9080 KB Output is correct
33 Correct 10 ms 9080 KB Output is correct
34 Correct 11 ms 9080 KB Output is correct
35 Correct 11 ms 8952 KB Output is correct
36 Correct 11 ms 8952 KB Output is correct
37 Correct 11 ms 9080 KB Output is correct
38 Correct 11 ms 8952 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8952 KB Output is correct
2 Correct 10 ms 8952 KB Output is correct
3 Correct 10 ms 8952 KB Output is correct
4 Correct 11 ms 8952 KB Output is correct
5 Correct 10 ms 8956 KB Output is correct
6 Correct 10 ms 8952 KB Output is correct
7 Correct 10 ms 8952 KB Output is correct
8 Correct 10 ms 8952 KB Output is correct
9 Correct 10 ms 8952 KB Output is correct
10 Correct 10 ms 8952 KB Output is correct
11 Correct 12 ms 8952 KB Output is correct
12 Correct 10 ms 8952 KB Output is correct
13 Correct 10 ms 8952 KB Output is correct
14 Correct 10 ms 8952 KB Output is correct
15 Correct 10 ms 8952 KB Output is correct
16 Correct 10 ms 8940 KB Output is correct
17 Correct 10 ms 8956 KB Output is correct
18 Correct 10 ms 8952 KB Output is correct
19 Correct 209 ms 15360 KB Output is correct
20 Correct 212 ms 16532 KB Output is correct
21 Correct 220 ms 17052 KB Output is correct
22 Correct 213 ms 17464 KB Output is correct
23 Correct 164 ms 16888 KB Output is correct
24 Correct 116 ms 16896 KB Output is correct
25 Correct 248 ms 19164 KB Output is correct
26 Correct 163 ms 23368 KB Output is correct
27 Correct 277 ms 24268 KB Output is correct
28 Correct 553 ms 35452 KB Output is correct
29 Correct 623 ms 34880 KB Output is correct
30 Correct 274 ms 24264 KB Output is correct
31 Correct 272 ms 24132 KB Output is correct
32 Correct 340 ms 24208 KB Output is correct
33 Correct 470 ms 23032 KB Output is correct
34 Correct 431 ms 23800 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8952 KB Output is correct
2 Correct 10 ms 8952 KB Output is correct
3 Correct 10 ms 8952 KB Output is correct
4 Correct 11 ms 8952 KB Output is correct
5 Correct 10 ms 8956 KB Output is correct
6 Correct 10 ms 8952 KB Output is correct
7 Correct 10 ms 8952 KB Output is correct
8 Correct 10 ms 8952 KB Output is correct
9 Correct 10 ms 8952 KB Output is correct
10 Correct 10 ms 8952 KB Output is correct
11 Correct 12 ms 8952 KB Output is correct
12 Correct 10 ms 8952 KB Output is correct
13 Correct 10 ms 8952 KB Output is correct
14 Correct 10 ms 8952 KB Output is correct
15 Correct 10 ms 8952 KB Output is correct
16 Correct 10 ms 8940 KB Output is correct
17 Correct 10 ms 8956 KB Output is correct
18 Correct 10 ms 8952 KB Output is correct
19 Correct 10 ms 8952 KB Output is correct
20 Correct 10 ms 8952 KB Output is correct
21 Correct 11 ms 9080 KB Output is correct
22 Correct 11 ms 9080 KB Output is correct
23 Correct 11 ms 8956 KB Output is correct
24 Correct 11 ms 8952 KB Output is correct
25 Correct 11 ms 9080 KB Output is correct
26 Correct 12 ms 8952 KB Output is correct
27 Correct 11 ms 8952 KB Output is correct
28 Correct 11 ms 9080 KB Output is correct
29 Correct 12 ms 9080 KB Output is correct
30 Correct 12 ms 9012 KB Output is correct
31 Correct 11 ms 9080 KB Output is correct
32 Correct 11 ms 9080 KB Output is correct
33 Correct 10 ms 9080 KB Output is correct
34 Correct 11 ms 9080 KB Output is correct
35 Correct 11 ms 8952 KB Output is correct
36 Correct 11 ms 8952 KB Output is correct
37 Correct 11 ms 9080 KB Output is correct
38 Correct 11 ms 8952 KB Output is correct
39 Correct 209 ms 15360 KB Output is correct
40 Correct 212 ms 16532 KB Output is correct
41 Correct 220 ms 17052 KB Output is correct
42 Correct 213 ms 17464 KB Output is correct
43 Correct 164 ms 16888 KB Output is correct
44 Correct 116 ms 16896 KB Output is correct
45 Correct 248 ms 19164 KB Output is correct
46 Correct 163 ms 23368 KB Output is correct
47 Correct 277 ms 24268 KB Output is correct
48 Correct 553 ms 35452 KB Output is correct
49 Correct 623 ms 34880 KB Output is correct
50 Correct 274 ms 24264 KB Output is correct
51 Correct 272 ms 24132 KB Output is correct
52 Correct 340 ms 24208 KB Output is correct
53 Correct 470 ms 23032 KB Output is correct
54 Correct 431 ms 23800 KB Output is correct
55 Correct 23 ms 9848 KB Output is correct
56 Correct 25 ms 9980 KB Output is correct
57 Correct 140 ms 17960 KB Output is correct
58 Correct 77 ms 18316 KB Output is correct
59 Correct 163 ms 23400 KB Output is correct
60 Correct 777 ms 37368 KB Output is correct
61 Correct 285 ms 24748 KB Output is correct
62 Correct 362 ms 25972 KB Output is correct
63 Correct 514 ms 25968 KB Output is correct
64 Correct 788 ms 27096 KB Output is correct
65 Correct 423 ms 25236 KB Output is correct
66 Correct 741 ms 32928 KB Output is correct
67 Correct 196 ms 28812 KB Output is correct
68 Correct 392 ms 25836 KB Output is correct
69 Correct 389 ms 26224 KB Output is correct
70 Correct 380 ms 25132 KB Output is correct