oj.uz

Submission #978836

# Submission time Handle Problem Language Result Execution time Memory
978836 2024-05-09T18:36:23 Z kwongweng Race (IOI11_race) C++17
100 / 100
 378 ms 87092 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef vector<vector<ll>> vll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ms memset
#define fi first
#define se second

const int mxn = 2e5+1;
vii g[mxn]; vi p(mxn);
map<int,int> S[mxn]; 
int ans;
vector<ll> dist(mxn); // # kilometres from root
vi dist2(mxn); //# highways from root
int k;

//compute distance to root
void dfs1(int u){
  for (ii edge : g[u]){
    int v = edge.fi; int w = edge.se;
    if (p[u]==v) continue;
    p[v] = u; dist[v] = dist[u]+w;
    dist2[v] = dist2[u]+1; dfs1(v);
  }
}

//small to large merging
vi add(mxn); //S[v][D] denote the closest child with distance D+add[v]
void dfs2(int u){
  S[u][0] = u;
  for (ii edge : g[u]){
    int v = edge.fi; int w = edge.se;
    if (p[u]==v) continue;
    dfs2(v);
    add[v]+=w;
    if (S[u].size()<S[v].size()) {swap(S[u],S[v]); swap(add[u],add[v]);}
    for (auto d : S[v]){
      int D = d.fi + add[v] + add[u];
      if (S[u].find(k-D) != S[u].end()){
        int v1 = S[u][k-D], v2 = d.se;
        //cout<<"Candidates "<<v1<<" "<<v2<<"\n";
        ans = min(ans, dist2[v1] + dist2[v2] - 2*dist2[u]);
      }
    }
    for (auto d : S[v]){
      int D = d.fi + add[v] - add[u];
      if (S[u].find(D) != S[u].end()){
        int v1 = S[u][D]; int v2 = d.se;
        if (dist2[v2] < dist2[v1]) S[u][D] = v2;
      }else{
        S[u][D] = d.se;
      }
    }
  }
  /*
  cout<<u<<"add " << add[u] <<"\n";
  for (auto d : S[u]){
    cout<<d.fi<<" "<<d.se<<"\n";
  }
  */
}

int best_path(int N, int K, int H[][2], int L[])
{
  k = K;
  ans = N;
  FOR(i,0,N-1){
    g[H[i][0]].pb({H[i][1],L[i]});
    g[H[i][1]].pb({H[i][0],L[i]});
  } 
  dfs1(0); dfs2(0);
  if (ans==N) ans = -1;
  return ans;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22108 KB Output is correct
2 Correct 6 ms 22004 KB Output is correct
3 Correct 5 ms 22108 KB Output is correct
4 Correct 5 ms 22108 KB Output is correct
5 Correct 5 ms 22108 KB Output is correct
6 Correct 5 ms 22104 KB Output is correct
7 Correct 5 ms 22108 KB Output is correct
8 Correct 5 ms 22108 KB Output is correct
9 Correct 5 ms 22104 KB Output is correct
10 Correct 5 ms 22108 KB Output is correct
11 Correct 6 ms 22108 KB Output is correct
12 Correct 6 ms 22108 KB Output is correct
13 Correct 5 ms 22108 KB Output is correct
14 Correct 5 ms 22108 KB Output is correct
15 Correct 6 ms 22108 KB Output is correct
16 Correct 6 ms 22104 KB Output is correct
17 Correct 5 ms 22104 KB Output is correct
18 Correct 6 ms 22108 KB Output is correct
19 Correct 5 ms 21852 KB Output is correct
20 Correct 5 ms 22108 KB Output is correct
21 Correct 6 ms 22284 KB Output is correct
22 Correct 7 ms 22260 KB Output is correct
23 Correct 6 ms 22108 KB Output is correct
24 Correct 6 ms 22108 KB Output is correct
25 Correct 7 ms 22280 KB Output is correct
26 Correct 6 ms 22288 KB Output is correct
27 Correct 6 ms 22108 KB Output is correct
28 Correct 6 ms 22108 KB Output is correct
29 Correct 6 ms 22104 KB Output is correct
30 Correct 7 ms 22108 KB Output is correct
31 Correct 6 ms 22108 KB Output is correct
32 Correct 6 ms 22108 KB Output is correct
33 Correct 7 ms 22108 KB Output is correct
34 Correct 6 ms 22108 KB Output is correct
35 Correct 6 ms 22108 KB Output is correct
36 Correct 6 ms 22108 KB Output is correct
37 Correct 6 ms 22108 KB Output is correct
38 Correct 6 ms 22308 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22108 KB Output is correct
2 Correct 6 ms 22004 KB Output is correct
3 Correct 5 ms 22108 KB Output is correct
4 Correct 5 ms 22108 KB Output is correct
5 Correct 5 ms 22108 KB Output is correct
6 Correct 5 ms 22104 KB Output is correct
7 Correct 5 ms 22108 KB Output is correct
8 Correct 5 ms 22108 KB Output is correct
9 Correct 5 ms 22104 KB Output is correct
10 Correct 5 ms 22108 KB Output is correct
11 Correct 6 ms 22108 KB Output is correct
12 Correct 6 ms 22108 KB Output is correct
13 Correct 5 ms 22108 KB Output is correct
14 Correct 5 ms 22108 KB Output is correct
15 Correct 6 ms 22108 KB Output is correct
16 Correct 6 ms 22104 KB Output is correct
17 Correct 5 ms 22104 KB Output is correct
18 Correct 6 ms 22108 KB Output is correct
19 Correct 95 ms 39496 KB Output is correct
20 Correct 108 ms 39760 KB Output is correct
21 Correct 89 ms 39252 KB Output is correct
22 Correct 90 ms 38988 KB Output is correct
23 Correct 123 ms 48724 KB Output is correct
24 Correct 98 ms 41556 KB Output is correct
25 Correct 77 ms 40684 KB Output is correct
26 Correct 49 ms 47616 KB Output is correct
27 Correct 142 ms 46160 KB Output is correct
28 Correct 225 ms 80468 KB Output is correct
29 Correct 218 ms 78932 KB Output is correct
30 Correct 143 ms 46084 KB Output is correct
31 Correct 156 ms 46160 KB Output is correct
32 Correct 197 ms 46068 KB Output is correct
33 Correct 184 ms 49512 KB Output is correct
34 Correct 273 ms 73752 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 22108 KB Output is correct
2 Correct 6 ms 22004 KB Output is correct
3 Correct 5 ms 22108 KB Output is correct
4 Correct 5 ms 22108 KB Output is correct
5 Correct 5 ms 22108 KB Output is correct
6 Correct 5 ms 22104 KB Output is correct
7 Correct 5 ms 22108 KB Output is correct
8 Correct 5 ms 22108 KB Output is correct
9 Correct 5 ms 22104 KB Output is correct
10 Correct 5 ms 22108 KB Output is correct
11 Correct 6 ms 22108 KB Output is correct
12 Correct 6 ms 22108 KB Output is correct
13 Correct 5 ms 22108 KB Output is correct
14 Correct 5 ms 22108 KB Output is correct
15 Correct 6 ms 22108 KB Output is correct
16 Correct 6 ms 22104 KB Output is correct
17 Correct 5 ms 22104 KB Output is correct
18 Correct 6 ms 22108 KB Output is correct
19 Correct 5 ms 21852 KB Output is correct
20 Correct 5 ms 22108 KB Output is correct
21 Correct 6 ms 22284 KB Output is correct
22 Correct 7 ms 22260 KB Output is correct
23 Correct 6 ms 22108 KB Output is correct
24 Correct 6 ms 22108 KB Output is correct
25 Correct 7 ms 22280 KB Output is correct
26 Correct 6 ms 22288 KB Output is correct
27 Correct 6 ms 22108 KB Output is correct
28 Correct 6 ms 22108 KB Output is correct
29 Correct 6 ms 22104 KB Output is correct
30 Correct 7 ms 22108 KB Output is correct
31 Correct 6 ms 22108 KB Output is correct
32 Correct 6 ms 22108 KB Output is correct
33 Correct 7 ms 22108 KB Output is correct
34 Correct 6 ms 22108 KB Output is correct
35 Correct 6 ms 22108 KB Output is correct
36 Correct 6 ms 22108 KB Output is correct
37 Correct 6 ms 22108 KB Output is correct
38 Correct 6 ms 22308 KB Output is correct
39 Correct 95 ms 39496 KB Output is correct
40 Correct 108 ms 39760 KB Output is correct
41 Correct 89 ms 39252 KB Output is correct
42 Correct 90 ms 38988 KB Output is correct
43 Correct 123 ms 48724 KB Output is correct
44 Correct 98 ms 41556 KB Output is correct
45 Correct 77 ms 40684 KB Output is correct
46 Correct 49 ms 47616 KB Output is correct
47 Correct 142 ms 46160 KB Output is correct
48 Correct 225 ms 80468 KB Output is correct
49 Correct 218 ms 78932 KB Output is correct
50 Correct 143 ms 46084 KB Output is correct
51 Correct 156 ms 46160 KB Output is correct
52 Correct 197 ms 46068 KB Output is correct
53 Correct 184 ms 49512 KB Output is correct
54 Correct 273 ms 73752 KB Output is correct
55 Correct 16 ms 24412 KB Output is correct
56 Correct 11 ms 23340 KB Output is correct
57 Correct 54 ms 37952 KB Output is correct
58 Correct 41 ms 32708 KB Output is correct
59 Correct 75 ms 52560 KB Output is correct
60 Correct 211 ms 79312 KB Output is correct
61 Correct 174 ms 48728 KB Output is correct
62 Correct 150 ms 46080 KB Output is correct
63 Correct 201 ms 46164 KB Output is correct
64 Correct 378 ms 87092 KB Output is correct
65 Correct 355 ms 85440 KB Output is correct
66 Correct 233 ms 75264 KB Output is correct
67 Correct 137 ms 41668 KB Output is correct
68 Correct 293 ms 58448 KB Output is correct
69 Correct 312 ms 62160 KB Output is correct
70 Correct 289 ms 57000 KB Output is correct