oj.uz

Submission #978760

# Submission time Handle Problem Language Result Execution time Memory
978760 2024-05-09T15:24:33 Z kwongweng Race (IOI11_race) C++17
9 / 100
 310 ms 78932 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+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 (D > k+2e6) continue;
      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 (D > k+2e6) continue;
      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 6 ms 22104 KB Output is correct
2 Correct 6 ms 22108 KB Output is correct
3 Correct 7 ms 22108 KB Output is correct
4 Correct 6 ms 22108 KB Output is correct
5 Correct 5 ms 22108 KB Output is correct
6 Correct 6 ms 22108 KB Output is correct
7 Correct 6 ms 22108 KB Output is correct
8 Correct 6 ms 22108 KB Output is correct
9 Correct 6 ms 22108 KB Output is correct
10 Correct 7 ms 22104 KB Output is correct
11 Correct 6 ms 22108 KB Output is correct
12 Correct 6 ms 22108 KB Output is correct
13 Correct 6 ms 22108 KB Output is correct
14 Correct 6 ms 22108 KB Output is correct
15 Correct 6 ms 22020 KB Output is correct
16 Correct 6 ms 22108 KB Output is correct
17 Correct 6 ms 22108 KB Output is correct
18 Correct 6 ms 22108 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 22104 KB Output is correct
2 Correct 6 ms 22108 KB Output is correct
3 Correct 7 ms 22108 KB Output is correct
4 Correct 6 ms 22108 KB Output is correct
5 Correct 5 ms 22108 KB Output is correct
6 Correct 6 ms 22108 KB Output is correct
7 Correct 6 ms 22108 KB Output is correct
8 Correct 6 ms 22108 KB Output is correct
9 Correct 6 ms 22108 KB Output is correct
10 Correct 7 ms 22104 KB Output is correct
11 Correct 6 ms 22108 KB Output is correct
12 Correct 6 ms 22108 KB Output is correct
13 Correct 6 ms 22108 KB Output is correct
14 Correct 6 ms 22108 KB Output is correct
15 Correct 6 ms 22020 KB Output is correct
16 Correct 6 ms 22108 KB Output is correct
17 Correct 6 ms 22108 KB Output is correct
18 Correct 6 ms 22108 KB Output is correct
19 Correct 6 ms 22108 KB Output is correct
20 Correct 6 ms 22104 KB Output is correct
21 Correct 7 ms 22108 KB Output is correct
22 Correct 7 ms 22228 KB Output is correct
23 Correct 8 ms 22108 KB Output is correct
24 Correct 7 ms 22108 KB Output is correct
25 Correct 9 ms 22108 KB Output is correct
26 Correct 6 ms 22108 KB Output is correct
27 Correct 8 ms 22108 KB Output is correct
28 Correct 8 ms 22184 KB Output is correct
29 Correct 7 ms 22108 KB Output is correct
30 Correct 7 ms 22104 KB Output is correct
31 Correct 7 ms 22116 KB Output is correct
32 Correct 7 ms 22112 KB Output is correct
33 Correct 7 ms 22360 KB Output is correct
34 Correct 6 ms 22104 KB Output is correct
35 Incorrect 6 ms 22108 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 22104 KB Output is correct
2 Correct 6 ms 22108 KB Output is correct
3 Correct 7 ms 22108 KB Output is correct
4 Correct 6 ms 22108 KB Output is correct
5 Correct 5 ms 22108 KB Output is correct
6 Correct 6 ms 22108 KB Output is correct
7 Correct 6 ms 22108 KB Output is correct
8 Correct 6 ms 22108 KB Output is correct
9 Correct 6 ms 22108 KB Output is correct
10 Correct 7 ms 22104 KB Output is correct
11 Correct 6 ms 22108 KB Output is correct
12 Correct 6 ms 22108 KB Output is correct
13 Correct 6 ms 22108 KB Output is correct
14 Correct 6 ms 22108 KB Output is correct
15 Correct 6 ms 22020 KB Output is correct
16 Correct 6 ms 22108 KB Output is correct
17 Correct 6 ms 22108 KB Output is correct
18 Correct 6 ms 22108 KB Output is correct
19 Correct 99 ms 39800 KB Output is correct
20 Correct 98 ms 40532 KB Output is correct
21 Correct 103 ms 40100 KB Output is correct
22 Correct 112 ms 40304 KB Output is correct
23 Correct 130 ms 50004 KB Output is correct
24 Correct 99 ms 42832 KB Output is correct
25 Correct 83 ms 41040 KB Output is correct
26 Correct 55 ms 46968 KB Output is correct
27 Correct 177 ms 47696 KB Output is correct
28 Correct 226 ms 78932 KB Output is correct
29 Correct 230 ms 77904 KB Output is correct
30 Correct 148 ms 48224 KB Output is correct
31 Correct 147 ms 48228 KB Output is correct
32 Correct 209 ms 48276 KB Output is correct
33 Correct 185 ms 51792 KB Output is correct
34 Incorrect 310 ms 75464 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 22104 KB Output is correct
2 Correct 6 ms 22108 KB Output is correct
3 Correct 7 ms 22108 KB Output is correct
4 Correct 6 ms 22108 KB Output is correct
5 Correct 5 ms 22108 KB Output is correct
6 Correct 6 ms 22108 KB Output is correct
7 Correct 6 ms 22108 KB Output is correct
8 Correct 6 ms 22108 KB Output is correct
9 Correct 6 ms 22108 KB Output is correct
10 Correct 7 ms 22104 KB Output is correct
11 Correct 6 ms 22108 KB Output is correct
12 Correct 6 ms 22108 KB Output is correct
13 Correct 6 ms 22108 KB Output is correct
14 Correct 6 ms 22108 KB Output is correct
15 Correct 6 ms 22020 KB Output is correct
16 Correct 6 ms 22108 KB Output is correct
17 Correct 6 ms 22108 KB Output is correct
18 Correct 6 ms 22108 KB Output is correct
19 Correct 6 ms 22108 KB Output is correct
20 Correct 6 ms 22104 KB Output is correct
21 Correct 7 ms 22108 KB Output is correct
22 Correct 7 ms 22228 KB Output is correct
23 Correct 8 ms 22108 KB Output is correct
24 Correct 7 ms 22108 KB Output is correct
25 Correct 9 ms 22108 KB Output is correct
26 Correct 6 ms 22108 KB Output is correct
27 Correct 8 ms 22108 KB Output is correct
28 Correct 8 ms 22184 KB Output is correct
29 Correct 7 ms 22108 KB Output is correct
30 Correct 7 ms 22104 KB Output is correct
31 Correct 7 ms 22116 KB Output is correct
32 Correct 7 ms 22112 KB Output is correct
33 Correct 7 ms 22360 KB Output is correct
34 Correct 6 ms 22104 KB Output is correct
35 Incorrect 6 ms 22108 KB Output isn't correct
36 Halted 0 ms 0 KB -