oj.uz

Submission #988478

# Submission time Handle Problem Language Result Execution time Memory
988478 2024-05-24T20:02:44 Z HoriaHaivas Race (IOI11_race) C++14
31 / 100
 2476 ms 131416 KB 
/*
    "care a facut teste cu Lattice reduction attack e ciudat"
    "linistiti va putin"
    - 2023 -
*/
#include<bits/stdc++.h>
#include "race.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
 
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 (k<cost)
        return;
    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);
        }
    }
}
 
signed best_path(signed N, signed K, signed H[][2], signed 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(long long int)':
race.cpp:88:11: warning: unused variable 'i' [-Wunused-variable]
   88 |     int c,i;
      |           ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:119:11: warning: unused variable 'j' [-Wunused-variable]
  119 |     int i,j,c,x,y;
      |           ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 3 ms 5100 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 3 ms 4956 KB Output is correct
12 Correct 3 ms 5204 KB Output is correct
13 Correct 3 ms 4952 KB Output is correct
14 Correct 3 ms 4952 KB Output is correct
15 Correct 3 ms 4952 KB Output is correct
16 Correct 3 ms 4956 KB Output is correct
17 Correct 3 ms 4956 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 4956 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 3 ms 5100 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 3 ms 4956 KB Output is correct
12 Correct 3 ms 5204 KB Output is correct
13 Correct 3 ms 4952 KB Output is correct
14 Correct 3 ms 4952 KB Output is correct
15 Correct 3 ms 4952 KB Output is correct
16 Correct 3 ms 4956 KB Output is correct
17 Correct 3 ms 4956 KB Output is correct
18 Correct 3 ms 4956 KB Output is correct
19 Correct 3 ms 4956 KB Output is correct
20 Correct 3 ms 4956 KB Output is correct
21 Correct 4 ms 5212 KB Output is correct
22 Incorrect 4 ms 5412 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 4956 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 3 ms 5100 KB Output is correct
10 Correct 3 ms 4956 KB Output is correct
11 Correct 3 ms 4956 KB Output is correct
12 Correct 3 ms 5204 KB Output is correct
13 Correct 3 ms 4952 KB Output is correct
14 Correct 3 ms 4952 KB Output is correct
15 Correct 3 ms 4952 KB Output is correct
16 Correct 3 ms 4956 KB Output is correct
17 Correct 3 ms 4956 KB Output is correct
18 Correct 3 ms 4956 KB Output is correct
19 Correct 147 ms 16584 KB Output is correct
20 Correct 158 ms 16592 KB Output is correct
21 Correct 194 ms 16584 KB Output is correct
22 Correct 127 ms 16640 KB Output is correct
23 Correct 101 ms 17048 KB Output is correct
24 Correct 76 ms 16300 KB Output is correct
25 Correct 163 ms 22168 KB Output is correct
26 Correct 113 ms 27180 KB Output is correct
27 Correct 196 ms 28792 KB Output is correct
28 Correct 1257 ms 83028 KB Output is correct
29 Correct 947 ms 78480 KB Output is correct
30 Correct 196 ms 28792 KB Output is correct
31 Correct 187 ms 28792 KB Output is correct
32 Correct 327 ms 28812 KB Output is correct
33 Correct 304 ms 27644 KB Output is correct
34 Correct 2476 ms 131416 KB Output is correct

Subtask #4
0 / 57.0

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