Submission #1025305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025305		mindiyak	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <string>
#include <iostream>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<int, int> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define nl endl
#define S second
#define lb lower_bound
#define ub upper_bound
#define aint(x) x.begin(), x.end()
#define raint(x) x.rbegin(), x.rend()
#define ins insert
const int MOD = 1000000007;
#include "race.h"
 
/*
1.BFS numer of children (priority queue with visited)
2.Check children nodes with each other (set with upper and lower bound)
3.Save children distances to the parent node (save a set with distances to each leaf)
 */
 
vector<vpi> paths(2e5+3,vpi());
vector<map<ll,pair<ll,ll>>> dist(2e5+3,map<ll,pair<ll,ll>>());
vector<vector<pair<ll,ll>>> distances(2e5+3,vector<pair<int,int>>(1e6+10));
vi children(2e5+3);
vi parent(2e5+3,-1);
vl parent_dist(2e5+3,-1);
 
void dfs(int pos,int prev){
  int sum = 1;
  for(auto node:paths[pos]){
    if(node.F == prev)continue;
    parent[node.F] = pos;
    parent_dist[node.F] = node.S;
    dfs(node.F,pos);
    sum += children[node.F];
  }
  children[pos] = sum;
}
 
int best_path(int N, int K, int H[][2], int L[])
{
  FOR(i,0,N-1){
    paths[H[i][0]].pb({H[i][1],L[i]});
    paths[H[i][1]].pb({H[i][0],L[i]});
  }
 
  dfs(0,-1);
 
  // FOR(i,0,N)cout << children[i] << " ";
  // cout << endl;
  // FOR(i,0,N)cout << parent[i] << " ";
  // cout << endl;
  // FOR(i,0,N)cout << parent_dist[i] << " ";
  // cout << endl;
 
  priority_queue<pi> pq;
  FOR(i,0,N){
    pq.push({-children[i],i});
  }
 
  ll ans = 1e18;
 
  while(!pq.empty()){
    int node = pq.top().S;pq.pop();
    // cout << node << " | " << endl;
    for(auto a:dist[node]){
      // cout << "a " << a.F << " " << K-a.F;
      if(a.F > K)continue;
      if(dist[node].count(K-a.F)){
        // cout << " " << dist[node][K-a.F].S << " " << a.S.S << " " << a.S.F << " " << dist[node][K-a.F].F;
        if(dist[node][K-a.F].S != a.S.S){
          // cout << " ans - " << a.S.F+dist[node][K-a.F].F+1;
          ans = min(ans,a.S.F+dist[node][K-a.F].F+1);
        }
      }
      // cout << endl;
    }
 
    if(parent[node] == -1)continue;
 
    
    // cout << "b " << parent[node] << " " << parent_dist[node] << " " << 1 << " " << node  << endl;
    dist[parent[node]].insert({parent_dist[node],{1,node}});
    for(auto a:dist[node]){
      // cout << "c " << parent[node] << " " << parent_dist[node]+a.F << " " << a.S.F+1 << " " << node  << endl;
      if(parent_dist[node]+a.F == K){
 
        ans = min(ans, a.S.F+2);
      }
      if(parent_dist[node]+a.F >= K)continue;
      dist[parent[node]].insert({parent_dist[node]+a.F,{a.S.F+1,node}});
    }
    // cout << endl;
  }
 
  if(ans == 1e18)return -1;
  return ans-1;
}

Compilation message (stderr)

race.cpp:49:74: error: no matching function for call to 'std::vector<std::vector<std::pair<long long int, long long int> > >::vector(double, std::vector<std::pair<int, int> >)'
   49 | vector<vector<pair<ll,ll>>> distances(2e5+3,vector<pair<int,int>>(1e6+10));
      |                                                                          ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from race.cpp:2:
/usr/include/c++/10/bits/stl_vector.h:653:2: note: candidate: 'template<class _InputIterator, class> std::vector<_Tp, _Alloc>::vector(_InputIterator, _InputIterator, const allocator_type&) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = std::vector<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::vector<std::pair<long long int, long long int> > >]'
  653 |  vector(_InputIterator __first, _InputIterator __last,
      |  ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:653:2: note:   template argument deduction/substitution failed:
race.cpp:49:74: note:   deduced conflicting types for parameter '_InputIterator' ('double' and 'std::vector<std::pair<int, int> >')
   49 | vector<vector<pair<ll,ll>>> distances(2e5+3,vector<pair<int,int>>(1e6+10));
      |                                                                          ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from race.cpp:2:
/usr/include/c++/10/bits/stl_vector.h:625:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::initializer_list<_Tp>, const allocator_type&) [with _Tp = std::vector<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::vector<std::pair<long long int, long long int> > >; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<std::vector<std::pair<long long int, long long int> > >]'
  625 |       vector(initializer_list<value_type> __l,
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:625:43: note:   no known conversion for argument 1 from 'double' to 'std::initializer_list<std::vector<std::pair<long long int, long long int> > >'
  625 |       vector(initializer_list<value_type> __l,
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:607:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&) [with _Tp = std::vector<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::vector<std::pair<long long int, long long int> > >; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<std::vector<std::pair<long long int, long long int> > >]'
  607 |       vector(vector&& __rv, const allocator_type& __m)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:607:23: note:   no known conversion for argument 1 from 'double' to 'std::vector<std::vector<std::pair<long long int, long long int> > >&&'
  607 |       vector(vector&& __rv, const allocator_type& __m)
      |              ~~~~~~~~~^~~~
/usr/include/c++/10/bits/stl_vector.h:589:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&, std::false_type) [with _Tp = std::vector<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::vector<std::pair<long long int, long long int> > >; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<std::vector<std::pair<long long int, long long int> > >; std::false_type = std::integral_constant<bool, false>]'
  589 |       vector(vector&& __rv, const allocator_type& __m, false_type)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:589:7: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/10/bits/stl_vector.h:585:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&, const allocator_type&, std::true_type) [with _Tp = std::vector<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::vector<std::pair<long long int, long long int> > >; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<std::vector<std::pair<long long int, long long int> > >; std::true_type = std::integral_constant<bool, true>]'
  585 |       vector(vector&& __rv, const allocator_type& __m, true_type) noexcept
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:585:7: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/10/bits/stl_vector.h:575:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&, const allocator_type&) [with _Tp = std::vector<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::vector<std::pair<long long int, long long int> > >; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<std::vector<std::pair<long long int, long long int> > >]'
  575 |       vector(const vector& __x, const allocator_type& __a)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:575:28: note:   no known conversion for argument 1 from 'double' to 'const std::vector<std::vector<std::pair<long long int, long long int> > >&'
  575 |       vector(const vector& __x, const allocator_type& __a)
      |              ~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:572:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>&&) [with _Tp = std::vector<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::vector<std::pair<long long int, long long int> > >]'
  572 |       vector(vector&&) noexcept = default;
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:572:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_vector.h:553:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const std::vector<_Tp, _Alloc>&) [with _Tp = std::vector<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::vector<std::pair<long long int, long long int> > >]'
  553 |       vector(const vector& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:553:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_vector.h:522:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const value_type&, const allocator_type&) [with _Tp = std::vector<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::vector<std::pair<long long int, long long int> > >; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = std::vector<std::pair<long long int, long long int> >; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<std::vector<std::pair<long long int, long long int> > >]'
  522 |       vector(size_type __n, const value_type& __value,
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:522:47: note:   no known conversion for argument 2 from 'std::vector<std::pair<int, int> >' to 'const value_type&' {aka 'const std::vector<std::pair<long long int, long long int> >&'}
  522 |       vector(size_type __n, const value_type& __value,
      |                             ~~~~~~~~~~~~~~~~~~^~~~~~~
/usr/include/c++/10/bits/stl_vector.h:510:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const allocator_type&) [with _Tp = std::vector<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::vector<std::pair<long long int, long long int> > >; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<std::vector<std::pair<long long int, long long int> > >]'
  510 |       vector(size_type __n, const allocator_type& __a = allocator_type())
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:510:51: note:   no known conversion for argument 2 from 'std::vector<std::pair<int, int> >' to 'const allocator_type&' {aka 'const std::allocator<std::vector<std::pair<long long int, long long int> > >&'}
  510 |       vector(size_type __n, const allocator_type& __a = allocator_type())
      |                             ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:497:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector(const allocator_type&) [with _Tp = std::vector<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::vector<std::pair<long long int, long long int> > >; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<std::vector<std::pair<long long int, long long int> > >]'
  497 |       vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:497:7: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/10/bits/stl_vector.h:487:7: note: candidate: 'std::vector<_Tp, _Alloc>::vector() [with _Tp = std::vector<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::vector<std::pair<long long int, long long int> > >]'
  487 |       vector() = default;
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:487:7: note:   candidate expects 0 arguments, 2 provided