oj.uz

Submission #988622

# Submission time Handle Problem Language Result Execution time Memory
988622 2024-05-25T10:14:37 Z HoriaHaivas Race (IOI11_race) C++14
0 / 100
 13 ms 25476 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];
int f[1000001];

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;
    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<=k;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:87:11: warning: unused variable 'i' [-Wunused-variable]
   87 |     int c,i;
      |           ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:118:11: warning: unused variable 'j' [-Wunused-variable]
  118 |     int i,j,c,x,y;
      |           ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Runtime error 13 ms 25476 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Runtime error 13 ms 25476 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Runtime error 13 ms 25476 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Runtime error 13 ms 25476 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -