oj.uz

Submission #988476

# Submission time Handle Problem Language Result Execution time Memory
988476 2024-05-24T20:00:51 Z HoriaHaivas Race (IOI11_race) C++14
31 / 100
 2837 ms 129840 KB 
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#include "race.h"

using namespace std;

struct edge
{
    int to;
    int cost;
};

int n,k;
int ans;
bool blocked[200001];
int sz[200001];
int h[200001][2];
int l[200001];
vector<edge> nodes[200001];
unordered_map<int,int> f;

void recalc(int node, int parent)
{
    sz[node]=1;
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to])
        {
            recalc(x.to,node);
            sz[node]+=sz[x.to];
        }
    }
}

int find_centroid(int compsize, int node, int parent)
{
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && sz[x.to]>compsize/2)
            return find_centroid(compsize,x.to,node);
    }
    return node;
}

void dfs(int node, int parent, int cost, int len)
{
    if (f.find(k-cost)!=f.end())
    ans=min(ans,len+f[k-cost]);
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to])
            dfs(x.to,node,cost+x.cost,len+1);
    }
}

void update(int node, int parent, int cost, int len)
{
    f[cost]=min(f[cost],len);
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to])
            update(x.to,node,cost+x.cost,len+1);
    }
}

void rem(int node, int parent, int cost)
{
    f[cost]=n+1;
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to])
            rem(x.to,node,cost+x.cost);
    }
}

void solve(int node)
{
    int c,i;
    recalc(node,-1);
    c=find_centroid(sz[node],node,-1);
    blocked[c]=1;
    f[0]=0;
    for (auto x : nodes[c])
    {
        if (!blocked[x.to])
        {
            dfs(x.to,c,x.cost,1);
            update(x.to,c,x.cost,1);
        }
    }
    for (auto x : nodes[c])
    {
        if (!blocked[x.to])
        {
            rem(x.to,c,x.cost);
        }
    }
    for (auto x : nodes[c])
    {
        if (!blocked[x.to])
        {
            solve(x.to);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    int i,j,c,x,y;
    n=N;
    k=K;
    for (i=0;i<=n;i++)
         f[i]=n+1;
    for (i=0; i<n; i++)
    {
        x=H[i][0];
        y=H[i][1];
        x++;
        y++;
        c=L[i];
        nodes[x].push_back({y,c});
        nodes[y].push_back({x,c});
    }
    ans=n+1;
    solve(1);
    if (ans!=n+1)
        return ans;
    else
        return -1;
}

Compilation message

race.cpp: In function 'void solve(int)':
race.cpp:80:11: warning: unused variable 'i' [-Wunused-variable]
   80 |     int c,i;
      |           ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:111:11: warning: unused variable 'j' [-Wunused-variable]
  111 |     int i,j,c,x,y;
      |           ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 4 ms 5208 KB Output is correct
6 Correct 3 ms 5080 KB Output is correct
7 Correct 4 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 3 ms 5152 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 3 ms 4952 KB Output is correct
12 Correct 3 ms 5108 KB Output is correct
13 Correct 4 ms 4956 KB Output is correct
14 Correct 3 ms 4952 KB Output is correct
15 Correct 3 ms 4956 KB Output is correct
16 Correct 3 ms 4956 KB Output is correct
17 Correct 3 ms 5000 KB Output is correct
18 Correct 3 ms 4956 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 4 ms 5208 KB Output is correct
6 Correct 3 ms 5080 KB Output is correct
7 Correct 4 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 3 ms 5152 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 3 ms 4952 KB Output is correct
12 Correct 3 ms 5108 KB Output is correct
13 Correct 4 ms 4956 KB Output is correct
14 Correct 3 ms 4952 KB Output is correct
15 Correct 3 ms 4956 KB Output is correct
16 Correct 3 ms 4956 KB Output is correct
17 Correct 3 ms 5000 KB Output is correct
18 Correct 3 ms 4956 KB Output is correct
19 Correct 4 ms 4952 KB Output is correct
20 Correct 3 ms 4956 KB Output is correct
21 Correct 3 ms 5208 KB Output is correct
22 Incorrect 5 ms 5420 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 4 ms 5208 KB Output is correct
6 Correct 3 ms 5080 KB Output is correct
7 Correct 4 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 3 ms 5152 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 3 ms 4952 KB Output is correct
12 Correct 3 ms 5108 KB Output is correct
13 Correct 4 ms 4956 KB Output is correct
14 Correct 3 ms 4952 KB Output is correct
15 Correct 3 ms 4956 KB Output is correct
16 Correct 3 ms 4956 KB Output is correct
17 Correct 3 ms 5000 KB Output is correct
18 Correct 3 ms 4956 KB Output is correct
19 Correct 152 ms 14960 KB Output is correct
20 Correct 150 ms 15808 KB Output is correct
21 Correct 138 ms 15624 KB Output is correct
22 Correct 120 ms 16324 KB Output is correct
23 Correct 130 ms 16604 KB Output is correct
24 Correct 76 ms 16324 KB Output is correct
25 Correct 163 ms 21392 KB Output is correct
26 Correct 113 ms 26064 KB Output is correct
27 Correct 185 ms 26604 KB Output is correct
28 Correct 1483 ms 80780 KB Output is correct
29 Correct 1117 ms 76788 KB Output is correct
30 Correct 182 ms 27000 KB Output is correct
31 Correct 181 ms 27168 KB Output is correct
32 Correct 303 ms 27192 KB Output is correct
33 Correct 278 ms 26232 KB Output is correct
34 Correct 2837 ms 129840 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4952 KB Output is correct
2 Correct 2 ms 4952 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 4 ms 5208 KB Output is correct
6 Correct 3 ms 5080 KB Output is correct
7 Correct 4 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 3 ms 5152 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 3 ms 4952 KB Output is correct
12 Correct 3 ms 5108 KB Output is correct
13 Correct 4 ms 4956 KB Output is correct
14 Correct 3 ms 4952 KB Output is correct
15 Correct 3 ms 4956 KB Output is correct
16 Correct 3 ms 4956 KB Output is correct
17 Correct 3 ms 5000 KB Output is correct
18 Correct 3 ms 4956 KB Output is correct
19 Correct 4 ms 4952 KB Output is correct
20 Correct 3 ms 4956 KB Output is correct
21 Correct 3 ms 5208 KB Output is correct
22 Incorrect 5 ms 5420 KB Output isn't correct
23 Halted 0 ms 0 KB -