Submission #77167

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
77167	2018-09-23T07:19:42 Z	muradeyn	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

#include "race.h"
#include <bits/stdc++.h>
#define intt long long
#define FAST_READ ios_base::sync_with_stdio(0);cin.tie(0);
#define SIZE 200001
#define INF INT_MAX
#define F first
#define S second
#define in(a) scanf("%d",&a);
#define outn(a) printf("%d\n",&a);
#define outs(a) printf("%d ",&a);


using namespace std;

intt root , n , k , x , y , w , used[SIZE] , dp[SIZE] , co , cent = -1 , we , ans = -1;

vector< pair<intt,intt> >v[SIZE];

map< intt , intt > mp;

bool f = true;

void init() {
    for (int i = 1;i<=n;i++) {
        if (used[i] < 5 && used[i] > 0)used[i] = 0;
    }
}

void dfs(int s,int p) {
    co++;
    used[s] = 1;
    int sz = v[s].size();
    for (int i = 0;i<sz;i++) {
        int to = v[s][i].first;
        intt cost = v[s][i].second;
        if (to == p)continue;
        if (used[to] >= 1)continue;
        we += cost;
        dfs(to,s);
    }
}

void dfs2(int s,int p) {
    used[s] = 2;
    dp[s] = 1;
    bool f = true;
    int sz = v[s].size();
    for (int i = 0;i<sz;i++) {
        int to = v[s][i].first;
        if (used[to] >= 2)continue;
        dfs2(to,s);
        if (dp[to] > co / 2) f = false;
        dp[s] += dp[to];
    }
    if (f && cent == -1 && co - dp[s] <= co / 2) cent = s;
}

void dfs3(int s,int p,int len,intt cst) {
    used[s] = 3;
    if (cst == k) {
        if (ans == -1)ans = len;
        else ans = min(ans,len);
        return;
    }
    int sz = v[s].size();
    for (int i = 0;i<sz;i++) {
        int to = v[s][i].first;
        intt cost = v[s][i].second;
        if (to == p)continue;
        if (used[to] >= 3)continue;
        dfs3(to,s,len + 1,cst + cost);
    }
}

void dfs4(int s,int p,int len,intt cst) {
    used[s] = 4;
    //cout<<s - 1<<" "<<cst<<" "<<k<<endl;
    //char aa;
    //cin>>aa;
    if (cst > k)return;
    if (cst == k) {
        if (ans == -1)ans = len;
        else ans = min(ans,len);
        return;
    }
    else if (mp[k - cst] != 0) {
        if (ans == -1)ans = len + mp[k - cst];
        else ans = min(ans,len + mp[k - cst]);
    }
    int sz = v[s].size();
    //cout<<sz<<endl;
    for (int i = 0;i<sz;i++) {
        int to = v[s][i].first;
        intt cost = v[s][i].second;
        if (to == p)continue;
        if (used[to] >= 4)continue;
        dfs4(to,s,len + 1,cst + cost);
    }
    if (mp[cst] == 0)mp[cst] = len;
    else if (mp[cst] > len)mp[cst] = min(mp[cst],len);
}

int best_path(int N, int K, int h[][2], int l[])
{
    k = K;
    n = N;
    for (int i = 0;i<n - 1;i++) {
        x = h[i][0];
        y = h[i][1];
        x++;
        y++;
        v[x].push_back({y,l[i]});
        v[y].push_back({x,l[i]});
    }
    while (f) {
        f = false;
        init();
        for (int i = 1;i<=n;i++) {
            if (used[i] == 0) {
              co = 0; we = 0;
                dfs(i , -1);
                if (we < k || co == 1) continue;
                dp[i] = 0;
                cent = -1;
                dfs2(i,-1);
                if (cent == -1)continue;
                f = true;
                root = cent;
                dfs3(cent,-1,0,0);
                mp.clear();
                dfs4(cent,-1,0,0);
                used[cent] = 5;
            }
        }
    }
    return ans;
}

Compilation message

race.cpp: In function 'void dfs3(int, int, int, long long int)':
race.cpp:63:31: error: no matching function for call to 'min(long long int&, int&)'
         else ans = min(ans,len);
                               ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:2:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
race.cpp:63:31: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
         else ans = min(ans,len);
                               ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:2:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
race.cpp:63:31: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
         else ans = min(ans,len);
                               ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
race.cpp:63:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
         else ans = min(ans,len);
                               ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
race.cpp:63:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
         else ans = min(ans,len);
                               ^
race.cpp: In function 'void dfs4(int, int, int, long long int)':
race.cpp:84:31: error: no matching function for call to 'min(long long int&, int&)'
         else ans = min(ans,len);
                               ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:2:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
race.cpp:84:31: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
         else ans = min(ans,len);
                               ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:2:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
race.cpp:84:31: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
         else ans = min(ans,len);
                               ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
race.cpp:84:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
         else ans = min(ans,len);
                               ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
race.cpp:84:31: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
         else ans = min(ans,len);
                               ^
race.cpp:101:53: error: no matching function for call to 'min(std::map<long long int, long long int>::mapped_type&, int&)'
     else if (mp[cst] > len)mp[cst] = min(mp[cst],len);
                                                     ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:2:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
race.cpp:101:53: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
     else if (mp[cst] > len)mp[cst] = min(mp[cst],len);
                                                     ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:2:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
race.cpp:101:53: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
     else if (mp[cst] > len)mp[cst] = min(mp[cst],len);
                                                     ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
race.cpp:101:53: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
     else if (mp[cst] > len)mp[cst] = min(mp[cst],len);
                                                     ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
race.cpp:101:53: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
     else if (mp[cst] > len)mp[cst] = min(mp[cst],len);
                                                     ^