oj.uz

Submission #56452

# Submission time Handle Problem Language Result Execution time Memory
56452 2018-07-11T11:36:19 Z Bodo171 Race (IOI11_race) C++14
9 / 100
 3000 ms 263168 KB 
#include "race.h"
#include <vector>
#include <map>
#include <iostream>
using namespace std;
const int nmax=200005;
map<long long,int> m[nmax];
vector< pair<int,int> > v[nmax];
long long k;
long long L[nmax];
int rr[nmax],l[nmax],r[nmax],lev[nmax],w[nmax],p[nmax];
int mn,nr,paths,n,i;
void ver(int path,long long A,long long LCA,int lca,int x)
{
    //A+X-2*LCA=K
    //X=K-A+2*LCA
    if(m[path][k-A+2*LCA]&&m[path][k-A+2*LCA]+x-2*lca<mn)
        mn=m[path][k-A+2*LCA]+x-2*lca;
}
void baga(int path,long long A,int x)
{
    if((!m[path][A])||m[path][A]>x)
        m[path][A]=x;
}
void dfs(int x)
{
    int son=0,nod=0;
    rr[++nr]=x;l[x]=nr;w[x]=1;
    for(int i=0;i<v[x].size();i++)
        if(!w[v[x][i].first])
    {
        nod=v[x][i].first;
        lev[nod]=lev[x]+1;L[nod]=1LL*L[x]+v[x][i].second;
        dfs(nod);
        w[x]+=w[nod];
        if(w[nod]>w[son]) son=nod;
    }
    r[x]=nr;
    p[x]=p[son];
    if(!son) p[x]=++paths;
    for(int i=0;i<v[x].size();i++)
        if(w[v[x][i].first]<=w[x]&&son!=v[x][i].first)
    {
        nod=v[x][i].first;
        for(int j=l[nod];j<=r[nod];j++)
        {
            ver(p[x],L[rr[j]],L[x],lev[x],lev[rr[j]]);
        }
        for(int j=l[nod];j<=r[nod];j++)
        {
            baga(p[x],L[rr[j]],lev[rr[j]]);
        }
    }
    ver(p[x],L[x],L[x],lev[x],lev[x]);
    baga(p[x],L[x],l[x]);
}
int best_path(int N, int K, int H[][2], int L[])
{
  n=N,k=K;
  for(i=0;i<n-1;i++)
  {
      v[H[i][0]].push_back({H[i][1],L[i]});
      v[H[i][1]].push_back({H[i][0],L[i]});
  }
  lev[0]=1;mn=n+1;
  dfs(0);
  if(mn==n+1) mn=-1;
  return mn;
}

Compilation message

race.cpp: In function 'void dfs(int)':
race.cpp:29:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
race.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14456 KB Output is correct
2 Correct 18 ms 14600 KB Output is correct
3 Correct 21 ms 14712 KB Output is correct
4 Correct 15 ms 14712 KB Output is correct
5 Correct 17 ms 14712 KB Output is correct
6 Correct 16 ms 14716 KB Output is correct
7 Correct 15 ms 14864 KB Output is correct
8 Correct 15 ms 14864 KB Output is correct
9 Correct 15 ms 14864 KB Output is correct
10 Correct 15 ms 14884 KB Output is correct
11 Correct 16 ms 14884 KB Output is correct
12 Correct 15 ms 14928 KB Output is correct
13 Correct 15 ms 14932 KB Output is correct
14 Correct 15 ms 14932 KB Output is correct
15 Correct 18 ms 14932 KB Output is correct
16 Correct 17 ms 14932 KB Output is correct
17 Correct 17 ms 14932 KB Output is correct
18 Correct 17 ms 14932 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14456 KB Output is correct
2 Correct 18 ms 14600 KB Output is correct
3 Correct 21 ms 14712 KB Output is correct
4 Correct 15 ms 14712 KB Output is correct
5 Correct 17 ms 14712 KB Output is correct
6 Correct 16 ms 14716 KB Output is correct
7 Correct 15 ms 14864 KB Output is correct
8 Correct 15 ms 14864 KB Output is correct
9 Correct 15 ms 14864 KB Output is correct
10 Correct 15 ms 14884 KB Output is correct
11 Correct 16 ms 14884 KB Output is correct
12 Correct 15 ms 14928 KB Output is correct
13 Correct 15 ms 14932 KB Output is correct
14 Correct 15 ms 14932 KB Output is correct
15 Correct 18 ms 14932 KB Output is correct
16 Correct 17 ms 14932 KB Output is correct
17 Correct 17 ms 14932 KB Output is correct
18 Correct 17 ms 14932 KB Output is correct
19 Correct 14 ms 14932 KB Output is correct
20 Correct 14 ms 14932 KB Output is correct
21 Correct 17 ms 15348 KB Output is correct
22 Correct 20 ms 15608 KB Output is correct
23 Correct 19 ms 15608 KB Output is correct
24 Correct 18 ms 15608 KB Output is correct
25 Correct 19 ms 15608 KB Output is correct
26 Correct 21 ms 15640 KB Output is correct
27 Correct 18 ms 15640 KB Output is correct
28 Correct 20 ms 15672 KB Output is correct
29 Correct 22 ms 15688 KB Output is correct
30 Correct 19 ms 15704 KB Output is correct
31 Correct 20 ms 15736 KB Output is correct
32 Correct 18 ms 15752 KB Output is correct
33 Correct 19 ms 15768 KB Output is correct
34 Correct 21 ms 15784 KB Output is correct
35 Correct 19 ms 15860 KB Output is correct
36 Incorrect 19 ms 15944 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14456 KB Output is correct
2 Correct 18 ms 14600 KB Output is correct
3 Correct 21 ms 14712 KB Output is correct
4 Correct 15 ms 14712 KB Output is correct
5 Correct 17 ms 14712 KB Output is correct
6 Correct 16 ms 14716 KB Output is correct
7 Correct 15 ms 14864 KB Output is correct
8 Correct 15 ms 14864 KB Output is correct
9 Correct 15 ms 14864 KB Output is correct
10 Correct 15 ms 14884 KB Output is correct
11 Correct 16 ms 14884 KB Output is correct
12 Correct 15 ms 14928 KB Output is correct
13 Correct 15 ms 14932 KB Output is correct
14 Correct 15 ms 14932 KB Output is correct
15 Correct 18 ms 14932 KB Output is correct
16 Correct 17 ms 14932 KB Output is correct
17 Correct 17 ms 14932 KB Output is correct
18 Correct 17 ms 14932 KB Output is correct
19 Correct 335 ms 49104 KB Output is correct
20 Correct 379 ms 50328 KB Output is correct
21 Correct 293 ms 52192 KB Output is correct
22 Correct 323 ms 53672 KB Output is correct
23 Correct 523 ms 83136 KB Output is correct
24 Correct 317 ms 83136 KB Output is correct
25 Execution timed out 3040 ms 263168 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14456 KB Output is correct
2 Correct 18 ms 14600 KB Output is correct
3 Correct 21 ms 14712 KB Output is correct
4 Correct 15 ms 14712 KB Output is correct
5 Correct 17 ms 14712 KB Output is correct
6 Correct 16 ms 14716 KB Output is correct
7 Correct 15 ms 14864 KB Output is correct
8 Correct 15 ms 14864 KB Output is correct
9 Correct 15 ms 14864 KB Output is correct
10 Correct 15 ms 14884 KB Output is correct
11 Correct 16 ms 14884 KB Output is correct
12 Correct 15 ms 14928 KB Output is correct
13 Correct 15 ms 14932 KB Output is correct
14 Correct 15 ms 14932 KB Output is correct
15 Correct 18 ms 14932 KB Output is correct
16 Correct 17 ms 14932 KB Output is correct
17 Correct 17 ms 14932 KB Output is correct
18 Correct 17 ms 14932 KB Output is correct
19 Correct 14 ms 14932 KB Output is correct
20 Correct 14 ms 14932 KB Output is correct
21 Correct 17 ms 15348 KB Output is correct
22 Correct 20 ms 15608 KB Output is correct
23 Correct 19 ms 15608 KB Output is correct
24 Correct 18 ms 15608 KB Output is correct
25 Correct 19 ms 15608 KB Output is correct
26 Correct 21 ms 15640 KB Output is correct
27 Correct 18 ms 15640 KB Output is correct
28 Correct 20 ms 15672 KB Output is correct
29 Correct 22 ms 15688 KB Output is correct
30 Correct 19 ms 15704 KB Output is correct
31 Correct 20 ms 15736 KB Output is correct
32 Correct 18 ms 15752 KB Output is correct
33 Correct 19 ms 15768 KB Output is correct
34 Correct 21 ms 15784 KB Output is correct
35 Correct 19 ms 15860 KB Output is correct
36 Incorrect 19 ms 15944 KB Output isn't correct
37 Halted 0 ms 0 KB -