oj.uz

Submission #479609

# Submission time Handle Problem Language Result Execution time Memory
479609 2021-10-12T10:20:19 Z kamalsharmaa9 Race (IOI11_race) C++14
9 / 100
 112 ms 86364 KB 
//https://pastebin.com/jVURaNCJ
#include<bits/stdc++.h>
#include <cstdio>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define N              200005
#define ff              first
#define ss              second
#define int         long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)


void c_p_c()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif

}
vector<int>gr[N];
map<int, int>edge[N];
map<int, int>m[N];
int depth[N];
int fin_ans = inf;
int val[N];
int k;
int dfs1(int node, int par)
{

  int ans = 0;
  for (auto child : gr[node])
  {
    if (child != par)
    {

      ans = max(ans, dfs1(child, node) + 1);
    }
  }
  return depth[node] = ans;
}
int dfs(int node, int par)
{
  int sz = 0;
  int ind;
  int not_child = 1;
  for (auto child : gr[node])
  {
    if (child != par )
    {
      not_child = 0;
      int temp = dfs(child, node);
      if (temp > sz)
      {
        sz = temp;
        ind = child;
      }
    }
  }
  if (not_child == 1) {
    val[node] = 0;
    depth[node] = 0;
    return 0;
  }
  for (auto child : gr[node])
  {
    if (child == par)
      continue;
    int to_find = k - edge[node][child];
    if (to_find == 0)
      fin_ans = 1;
    to_find = to_find - val[child];
    if (m[child].find(to_find) != m[child].end())
    {
      fin_ans = min(fin_ans, 1 + depth[child] - m[child][to_find]);
    }
  }
  m[node].swap(m[ind]);
  depth[node] = depth[ind] + 1;
  val[node] = val[ind] + edge[node][ind];
  m[node][edge[node][ind] - val[node]] = depth[node] - 1;
  m[ind].clear();
  ////////////////////////////////alll deal with child to node
  // and inserted bigger_child and done with that
  for (auto child : gr[node])
  {
    if (child != par && child != ind)
    {
      for (auto i : m[child])
      {
        int num = i.ff + val[child] + edge[node][child];
        int to_find = k - num - val[node];
        if (m[node].find(to_find) != m[node].end())
        {

          fin_ans = min(fin_ans, depth[node] - m[node][to_find] + depth[child] - i.ss + 1);
        }
      }
      int findd = k - edge[node][child];
      if (m[node].find(findd) != m[node].end())
      {
        fin_ans = min(fin_ans, depth[node] - m[node][findd] + 1);
      }
      for (auto i : m[child])
      {
        int num = i.ff + val[child];

        int to_insert = num - val[node];
        if (num > k)
          continue;
        int newd = depth[node] - 1 - (depth[child] - i.ss);
        if (m[node].find(to_insert) != m[node].end())
        {
          if (m[node][to_insert] < newd)
            m[node][to_insert] = newd;
        }
        else
          m[node][to_insert] = newd;

      }
      m[node][edge[node][child] - val[node]] = depth[node] - 1;
      m[child].clear();
    }


  }
  return m[node].size();
}

int32_t best_path(int32_t n, int32_t K, int32_t H[][2], int32_t L[]) {
  int i, a, b, c;
  k = (int)K;
  for (int i = 0; i <= n; i++)
  {
    gr[i].clear();
    m[i].clear();
    depth[i] = 0;
    val[i] = 0;
    edge[i].clear();
  }
  fin_ans = inf;
  //edge.clear();
  for (i = 0; i < n - 1; i++) {
    a = H[i][0]; b = H[i][1]; c = L[i];
    a++; b++;
    edge[a][b] = c;
    edge[b][a] = c;
    gr[a].pb(b);
    gr[b].pb(a);
  }

  //dfs1(1, 0);

  dfs(1, 0);
  if (fin_ans == inf )
    return -1;
  return (int32_t)fin_ans;

}

Compilation message

race.cpp: In function 'void c_p_c()':
race.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   freopen("output.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 12 ms 23756 KB Output is correct
3 Correct 12 ms 23756 KB Output is correct
4 Correct 12 ms 23836 KB Output is correct
5 Correct 13 ms 23844 KB Output is correct
6 Correct 13 ms 23840 KB Output is correct
7 Correct 14 ms 23768 KB Output is correct
8 Correct 13 ms 23884 KB Output is correct
9 Correct 12 ms 23828 KB Output is correct
10 Correct 12 ms 23756 KB Output is correct
11 Correct 13 ms 23740 KB Output is correct
12 Correct 14 ms 23776 KB Output is correct
13 Correct 13 ms 23844 KB Output is correct
14 Correct 12 ms 23756 KB Output is correct
15 Correct 12 ms 23848 KB Output is correct
16 Correct 14 ms 23812 KB Output is correct
17 Correct 14 ms 23756 KB Output is correct
18 Correct 14 ms 23756 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 12 ms 23756 KB Output is correct
3 Correct 12 ms 23756 KB Output is correct
4 Correct 12 ms 23836 KB Output is correct
5 Correct 13 ms 23844 KB Output is correct
6 Correct 13 ms 23840 KB Output is correct
7 Correct 14 ms 23768 KB Output is correct
8 Correct 13 ms 23884 KB Output is correct
9 Correct 12 ms 23828 KB Output is correct
10 Correct 12 ms 23756 KB Output is correct
11 Correct 13 ms 23740 KB Output is correct
12 Correct 14 ms 23776 KB Output is correct
13 Correct 13 ms 23844 KB Output is correct
14 Correct 12 ms 23756 KB Output is correct
15 Correct 12 ms 23848 KB Output is correct
16 Correct 14 ms 23812 KB Output is correct
17 Correct 14 ms 23756 KB Output is correct
18 Correct 14 ms 23756 KB Output is correct
19 Incorrect 13 ms 23756 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 12 ms 23756 KB Output is correct
3 Correct 12 ms 23756 KB Output is correct
4 Correct 12 ms 23836 KB Output is correct
5 Correct 13 ms 23844 KB Output is correct
6 Correct 13 ms 23840 KB Output is correct
7 Correct 14 ms 23768 KB Output is correct
8 Correct 13 ms 23884 KB Output is correct
9 Correct 12 ms 23828 KB Output is correct
10 Correct 12 ms 23756 KB Output is correct
11 Correct 13 ms 23740 KB Output is correct
12 Correct 14 ms 23776 KB Output is correct
13 Correct 13 ms 23844 KB Output is correct
14 Correct 12 ms 23756 KB Output is correct
15 Correct 12 ms 23848 KB Output is correct
16 Correct 14 ms 23812 KB Output is correct
17 Correct 14 ms 23756 KB Output is correct
18 Correct 14 ms 23756 KB Output is correct
19 Runtime error 112 ms 86364 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 12 ms 23756 KB Output is correct
3 Correct 12 ms 23756 KB Output is correct
4 Correct 12 ms 23836 KB Output is correct
5 Correct 13 ms 23844 KB Output is correct
6 Correct 13 ms 23840 KB Output is correct
7 Correct 14 ms 23768 KB Output is correct
8 Correct 13 ms 23884 KB Output is correct
9 Correct 12 ms 23828 KB Output is correct
10 Correct 12 ms 23756 KB Output is correct
11 Correct 13 ms 23740 KB Output is correct
12 Correct 14 ms 23776 KB Output is correct
13 Correct 13 ms 23844 KB Output is correct
14 Correct 12 ms 23756 KB Output is correct
15 Correct 12 ms 23848 KB Output is correct
16 Correct 14 ms 23812 KB Output is correct
17 Correct 14 ms 23756 KB Output is correct
18 Correct 14 ms 23756 KB Output is correct
19 Incorrect 13 ms 23756 KB Output isn't correct
20 Halted 0 ms 0 KB -